language-agnostic - フィールドで動的計画法を使用したのはいつですか?

Question

現場の問題を解決するために動的計画法の概念を直接適用したのはいつですか? ナップザック問題のでっち上げのインスタンスを解決するためにそれを使用する場合、それをどのように適用できるかが明らかでない場合があります。

Answer 1

現場の問題を解決するためにメモ化を使用することは、より幅広い問題に適用できるため、おそらくより一般的です。DP は、フィボナッチ数 (難しい方法) や素数 (効率的な方法) の計算のように、重複する副問題がたくさんある場合にのみ実際に呼び出されます。

ちなみに、リンク先のページにはDP を使用するアルゴリズムのリストがあります。