動的プログラミングとは何ですか? [closed] 質問する

動的プログラミングとは、過去の知識を利用して将来の問題を容易に解決することです。

良い例としては、n=1,000,002 のフィボナッチ数列を解くことが挙げられます。

これは非常に長いプロセスになりますが、n=1,000,000 と n=1,000,001 の結果を示したらどうなるでしょうか。突然、問題が扱いやすくなります。

動的プログラミングは、文字列編集問題などの文字列問題でよく使用されます。問題のサブセットを解決し、その情報を使用して、より難しい元の問題を解決します。

動的プログラミングでは、通常、結果を何らかのテーブルに保存します。問題の答えが必要な場合は、テーブルを参照して、すでに答えがわかっているかどうかを確認します。わかっていない場合は、テーブル内のデータを使用して、答えへの足がかりを作ります。

Cormen Algorithms の本には、動的プログラミングに関する素晴らしい章があります。しかも、Google ブックスで無料で入手できます。ぜひご覧ください。ここ。