[解決済み] バックトラッキングとダイナミックプログラミングの違い

質問

動的計画法とバックトラッキングの違いは、DPではサブ問題のオーバーラップが可能なことくらいだと聞きました。

fib(n) = fib(n-1) + fib (n-2)

正しいですか？他に違いはありますか？

また、これらの技術を使って解決した一般的な問題も教えてほしい。

解決方法は？

動的計画法の代表的な実装は2つあります。 下から上へ と 上から下へ .

上から下への動的プログラミング は、普通の 再帰 中間的な小問題の解を記憶しておくことで、さらに強化される。ある小問題が2回目（3回目、4回目...）に発生したとき、ゼロから解くのではなく、前に記憶していた解法をすぐに使うのです。この手法は、以下のような名前で知られている。 メモ化 (iの前にrをつけない）。

フィボナッチ数列の例は、実はこれを説明するためのものなのです。フィボナッチ数列の再帰的な公式を使うだけですが、そのテーブルを作るために fib(i) を計算する必要がある場合、この問題に対するTop-to-bottom DPアルゴリズムが得られます（これにより、例えば fib(5) 2度目は、再度計算するのではなく、表から取得します）。

で ボトム・トゥ・トップ動的計画法 このアプローチも、部分解をメモリに保存することに基づいていますが、それらは異なる順序（小さいものから大きいものへ）で解かれ、結果としてアルゴリズムの一般構造は再帰的ではありません。 LCSアルゴリズム は、Bottom-to-top DPの典型的な例である。

なぜなら、元の問題全体を解くためにどの原始的な小問題が必要になるのか、また、小さな小問題からどの経路を通れば最も効率的に最終解に到達できるのかを予測することは、必ずしも容易ではないからです。