DAA-動的計画法

動的計画法は、最適化問題でも使用されます。分割統治法と同様に、動的計画法はサブ問題の解を組み合わせることによって問題を解決します。さらに、動的計画法アルゴリズムは、各サブ問題を1回だけ解決してから、その回答をテーブルに保存するため、毎回回答を再計算する作業を回避できます。

問題の2つの主要な特性は、与えられた問題が動的計画法を使用して解決できることを示唆しています。これらのプロパティはoverlapping sub-problems and optimal substructure。

重複するサブ問題

分割統治法と同様に、動的計画法もサブ問題の解決策を組み合わせます。これは主に、1つのサブ問題の解決が繰り返し必要な場合に使用されます。計算された解はテーブルに保存されるため、これらを再計算する必要はありません。したがって、この手法は、重複するサブ問題が存在する場合に必要です。

たとえば、二分探索には重複するサブ問題はありません。一方、フィボナッチ数の再帰的プログラムには、多くの重複するサブ問題があります。

与えられた問題の最適解がそのサブ問題の最適解を使用して得られる場合、与えられた問題は最適部分構造特性を持っています。

たとえば、最短経路問題には次の最適な部分構造特性があります。

ノードの場合 x ソースノードからの最短パスにあります u 宛先ノードへ v、次にからの最短経路 u に v からの最短経路の組み合わせです u に x、およびからの最短経路 x に v。

Floyd-WarshallやBellman-Fordなどの標準のAllPair Shortest Pathアルゴリズムは、動的計画法の典型的な例です。

動的計画法アルゴリズムは、次の4つのステップを使用して設計されています-