動的計画法とは
動的計画法（Dynamic Programming）は、対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法です。
動的計画法は特定のアルゴリズムではなく、考え方です。
動的計画法を適用するには、以下の条件が成立する必要があります。
- 最適な部分構造（optimal substructure）
- 重複する部分問題（overlapping subproblems）
- 後付けなし
最適な部分構造（optimal substructure）
最適な部分構造は、部分問題と元の問題との関係を規定するものです。
動的計画法は問題の最適解を見つけること、つまり問題に対する多数の解の中から最適なものを見つけ出すことです。
問題の最適解は、その部分問題の最適解によって決定されます。
最適な部分構造は、以下の2条件が成立していることを指します。
- 部分問題も同じ最適化問題が成立している。
- 部分問題間が独立している。
重複する部分問題（overlapping subproblems）
重複する部分問題は、部分問題間の関係を規定するものです。
同一の部分問題が繰り返し出現する場合、重複する部分問題の計算結果を記録し再利用する事により計算量を削減します。
後付けなし
ある状態が決定されると、それ以降の状態から影響を受けないことです。
つまり現在の状態の処理は、現在の状態にのみ影響します。
線形DP
動的計画法は以下の重要ポイントがあります。
- 状態定義
- 状態遷移
- 初期化
- 境界条件
状態定義は、部分問題をどのように表現するかということです。例えば、一般的にサイズがn個ある部分問題はdp[n]と定義します。この場合dp[n-1]はn-1番目の部分問題の解になります。
状態遷移は、部分問題間の関係を表現するものです。
線形DPの特徴は、状態は問題サイズiの小->大の順で導き、大きい問題の解は小さい問題の解に依存します。
ここで問題サイズiは、最初のi個の要素[0...i]の解を考える場合です。
状態定義： dp[n]:=dp[0...n]上の問題の解
状態遷移： dp[i] = f(dp[i-1], ..., dp[0])
上記状態定義と状態遷移から、大規模問題の状態は小規模問題にのみ関係し、問題の規模は変数iで完全に表されることがわかります。iの大きさは問題の大きさを表すので、iを小さいものから大きいものへとnに達するまで計算すると元の問題の解が得られ、これが線形DPとなります。
線形DPは問題の入力形式によって以下に分類できます。
- Single (dp[i])
- Double (dp[i][j])
- Matrix (dp[i][j])
Single
入力は1つのリストとなる問題です。
Single問題の状態定義は、dp[n]:=[0...n]上の問題です。
iより小さいO(1)個の部分問題に依存する
dp[i]は定数個の部分問題にのみ関係する問題です。
-
[leetcode]53. Maximum Subarray
dp[i] = nums[i] + max(dp[i - 1], 0) -
[leetcode]70. Climbing Stairs
dp[i] = dp[i-1] + dp[i-2] -
[leetcode]746. Min Cost Climbing Stairs
dp[i] = min(dp[i−1]+cost[i−1], dp[i−2]+cost[i−2]) -
[leetcode]790. Domino and Tromino Tiling
dp[i][0] = dp[i−1][3]
dp[i][1] = dp[i−1][0]+dp[i−1][2]
dp[i][2] = dp[i−1][0]+dp[i−1][1]
dp[i][3] = dp[i−1][0]+dp[i−1][1]+dp[i−1][2]+dp[i−1][3]
iより小さいO(N)個の部分問題に依存する
dp[i]は計算した全ての部分問題と関係する問題です。
-
[leetcode]300. Longest Increasing Subsequence
dp[i] = max(dp[0...j])+1, 0≤j<i & num[j]<num[i] -
[leetcode]139. Word Break
dp[i] = dp[j] && check(s[j...i−1])
部分問題は位置iにのみ関係する場合、dp[i]となります。
部分問題は別の指標k（長さ、数、次数、色など）と関係する場合、dp[i][k]となります。
kには二分探索、貪欲法などのアルゴリズムを適用する場合があります。
Double
入力は2つのリストとなる問題です。
サイズはそれぞれm,nの場合、2つの変数i,jで位置を表現します。
状態定義： dp[i][j]:=入力1[0...i],入力2[0...j]の時の解
状態遷移の例： dp[i][j]=f(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])
Matrix
入力は2次元配列となる問題です。