動的計画法は重要なアルゴリズムのパラダイムであり、問題をより小さなサブ問題に分割し、サブ問題の解を保存して重複計算を回避することで、時間効率を大幅に向上させます。
動的計画法の特徴#
サブ問題の分割は一般的なアルゴリズムのアプローチであり、分割統治法、動的計画法、バックトラックの中で重点が異なります。
- 分割統治法は問題を相互に独立した複数のサブ問題に再帰的に分割し、最小のサブ問題まで分割し、バックトラックでサブ問題の解を結合して元の問題の解を得ます。
- 動的計画法も問題を再帰的に分割しますが、分割統治法との主な違いは、動的計画法ではサブ問題が相互に依存していることであり、分割の過程で多くの重複するサブ問題が発生します。
- バックトラック法はすべての可能な解を試行し、バックトラックを使用して不要な探索を回避することで、元の問題の解を求めます。元の問題の解は一連の決定ステップで構成され、各決定ステップの前の部分列をサブ問題と見なすことができます。
動的計画法は最適化問題の解決によく使用されます。重複するサブ問題だけでなく、最適な部分構造と後方効果の 2 つの特徴も持っています。 - 最適な部分構造の定義：元の問題の最適解は、サブ問題の最適解から構築されます。
- 後方効果：特定の状態が与えられた場合、その将来の発展は現在の状態にのみ依存し、過去のすべての状態には依存しません。
動的計画法の解法の考え方#
以下の 2 つの問題を考えます：
- 問題が動的計画法の問題であるかどうかを判断する方法は？
- 動的計画法の問題を解くためのアプローチはどこから始めればよいですか？完全な手順は何ですか？
問題の判断#
問題に重複するサブ問題、最適な部分構造が含まれ、かつ後方効果を満たす場合、通常は動的計画法で解決するのに適しています。
通常、条件を緩めて、問題がバックトラックで解決するのに適しているかどうかを観察します。バックトラックで解決するのに適している問題は通常、「決定木モデル」を満たします。このような問題はツリー構造を使用して記述することができ、各ノードは 1 つの決定を表し、各パスは 1 つの決定シーケンスを表します。
言い換えれば、問題に明確な決定の概念が含まれ、解が一連の決定によって生成される場合、それは決定木モデルを満たし、通常はバックトラックで解決できます。
さらに、動的計画法の問題にはいくつかの「プラスポイント」があります：
- 問題に最大（小）または最多（小）などの最適化の記述が含まれている
- 問題の状態がリスト、多次元行列、または木で表され、状態とその周囲の状態との間に再帰的な関係が存在する
対応する「マイナスポイント」もいくつか存在します： - 問題の目標はすべての可能な解を見つけることであり、最適解を見つけることではありません
- 問題の記述に明らかな順列組み合わせの特徴があり、具体的な複数の解を返す必要があります。
問題の解決手順#
動的計画法の解決プロセスは、問題の性質と難易度によって異なる場合がありますが、通常は次の手順に従います：決定の記述、状態の定義、dp テーブルの構築、状態遷移方程式の導出、境界条件の確定など。