3

動的計画法について読んでいます。上手になるには練習と直感が必要だと読みましたが、このアドバイスは一般的なように思えます。
私にとって最も難しいのは、再帰式を理解することです。ソリューションで使用されている数式が直感的に理解できない場合があります。
たとえば、次の問題を読みました。

2 つの文字列 S と T があります。S が T に出現する回数を見つけるアルゴリズムを与えてください。S のすべての文字が T で連続して出現することは必須ではありません。

解決策は、次の再帰式に基づいていますが、私にとってはまったく直感的ではありません。

M(i, j) は、S の i 文字が T の j 文字に出現する回数を表すと仮定します。基本ケース:
i) j = 0 の場合は 0
ii) i = 0 の場合は 1

DPを介して問題を解決するための適切な再帰式を定義/見つけるのに役立つ、問題のある種の「分析」があるのではないかと思っていましたか?

4

2 に答える 2

0

ここのウィキペディアで非常によく説明されています:
「数学、コンピューターサイエンス、および経済学では、動的計画法は、複雑な問題をより単純な部分問題に分解することによって解決する方法です。重複部分の特性を示す問題に適用できます。 -問題と最適な部分構造 (以下で説明) 該当する場合、この方法は単純な方法よりもはるかに短い時間で済みます。

部分問題の重複と最適な部分構造についてもお読みください。

于 2013-02-02T11:31:47.600 に答える