動的計画法

動的計画法はどう速くするのか

動的計画法は、部分問題の答えを表に書き、同じ問いが来たら計算せずに表から読んで速くします。書き方は、再帰で上から解きながら覚えるメモ化と、小さい方から表を埋めるやり方の 2 つです。

素直な再帰は、同じ問いを何度も解き直す

素直な再帰が遅いのは、同じ小さな計算を何千回もくり返しているからです。

fib(5) は fib(4) と fib(3) を呼び、fib(4) もまた fib(3) を呼ぶので、fib(3) は 2 回解かれます。この重なりは下の段ほど膨らみます。

下の図で n を動かすと、fib(k) ごとに呼ばれた回数の棒が伸びます。「一度出た答えを覚えておく」を入れると、どの fib(k) も計算は 1 回ずつになります。

メモ化は、上から解きながら答えを覚える

メモ化 (memoization) は、関数が返した答えを引数ごとに覚え、同じ引数で呼ばれたら本体を動かさずに返す書き方です。素直な再帰の前に 1 行足すだけで書けます。

Python では標準の functools.cache を使います。公式文書によると lru_cache(maxsize=None) と同じ物で、答えは引数を鍵にした辞書に入るので、引数は数や文字列のようなハッシュできる値に限られます。

cache を付けた関数には cache_info() があり、表から読んだ回数 (hits) と、表に無くて本体を動かした回数 (misses) を返します。読んだ回数と動かした回数を足すと、呼ばれた回数になります。

下から埋めるやり方は、小さい方から表を作る

下から埋めるやり方は、いちばん小さな部分問題の答えを表の先頭に置き、漸化式を使って小さい方から順にマスを埋めていく書き方です。再帰を使わず、ループ 1 本で書けます。

フィボナッチ数なら、表 dp の dp[0] に 0、dp[1] に 1 を置き、k を 2 から n まで進めながら dp[k] = dp[k − 1] + dp[k − 2] で埋めます。dp[k] を埋めるときには、要る 2 つのマスはもう埋まっています。

下の図で n を上げると、埋まるマスが増えます。「変数 2 本に圧縮」を入れると、直前の 2 つしか読まないので表の全部は要らないことが分かります。

2 つの書き方を並べると、次の通りです。

部分問題と漸化式を立てる

動的計画法が使えるのは、大きな問題の答えが小さな問題の答えから作れて、その小さな問題が何度も出てくるときです。前の性質を最適部分構造、後の性質を部分問題の重なりと呼びます。

部分問題 (ぶぶんもんだい) は、元の問題を小さくした同じ形の問題です。漸化式 (ぜんかしき) は、前の答えから次の答えを作る式です。

階段の上り方で考えます。1 回に 1 段か 2 段上れるとき、n 段目に着く上り方は何通りかという問題です。最後の 1 歩は、n − 1 段目からの 1 段か、n − 2 段目からの 2 段なので、上り方はその 2 つの和になります。

ways(n) = ways(n - 1)
        + ways(n - 2)
ways(0) = 1, ways(1) = 1

この式はフィボナッチ数と同じ形です。部分問題は「k 段目への上り方」で、表の 1 マスが 1 つの答えです。