女性向けエンジニアスクール
3秒でわかる
小さな部分問題の答えを記録して使い回し、重複した計算を消す設計手法。指数時間で終わらない探索を現実的な時間に落とすために使います。
もう少し詳しく
どういうものか
動的計画法は、大きな問題を小さな部分問題に分け、一度求めた答えを表に記録して二度と計算し直さない手法です。英語の頭文字から DP とも書きます。使える条件は二つあり、大きな問題の答えが部分問題の答えから組み立てられること、そして同じ部分問題が何度も現れることです。
書き方は二通りあります。再帰で書いて計算結果を辞書に控えるメモ化と、小さい方から順に配列を埋めていく漸化式型です。どちらも記録して使い回す点は同じです。
なぜ必要か
素直な再帰は同じ計算を何度も繰り返します。フィボナッチ数を定義どおり再帰で書くと、n が 40 を超えたあたりで待たされ、50 では終わりません。呼び出しの木が枝分かれするたびに同じ引数の計算が重複するためです。記録を挟むだけで、計算回数は引数の種類の数まで減ります。
具体例
同じ問題を三通りで書くと差がはっきりします。
from functools import lru_cache
# 素直な再帰。指数時間
def fib_slow(n):
return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
# メモ化。上から下へ
@lru_cache(maxsize=<a href="/glossary/none" class="text-primary font-medium underline underline-offset-2 hover:text-primary-dark">None</a>)
def fib_memo(n):
return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
# 表を埋める。下から上へ
def fib_table(n):
dp = [0, 1] + [0] * (n - 1)
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fib_memo(90), fib_table(90))つまずきやすいところ
最大の難所は、何を表の添字にするかを決めるところです。フィボナッチは添字が一つですが、ナップサック問題では「何個目まで見たか」と「残り容量」の二つが要ります。答えを一意に決めるのに必要な情報を過不足なく並べたものが状態で、ここを外すと正しい漸化式が立ちません。
初期値と埋める順序も落とし穴です。参照する側より先に参照される側が埋まっている必要があります。表を更新する順を逆にするだけで答えが変わる問題もあり、一次元に圧縮したナップサックで容量を降順に回すのはその一例です。メモ化は再帰が深くなるため、Python では上限に達して停止することがあり、その場合は表を埋める形へ書き換えます。
覚え方
「同じ計算を二度しない」。総当たりを書いてみて、同じ引数が二度出たら DP の出番だと判断できます。
