動的計画法（DP）とは？メモ化とタブulationをわかりやすく解説

動的計画法は、小さな部分問題の答えを保存し、あとで再利用することで問題を解く方法です。同じ部分問題が何度も現れ、全体の答えをそれらの小さな答えから組み立てられるときに役立ちます。

代表的な方法は、メモ化とタブulationの2つです。メモ化は再帰的な解法の途中で答えを保存します。タブulationは、通常は配列や表を使って、下から順に答えを埋めていきます。

動的計画法が有効なとき

動的計画法が役立つのは、2つの条件がそろうときです。

1つ目は、部分問題が重複していることです。つまり、同じ中間結果が複数回必要になります。2つ目は、大きな答えを小さな答えから一貫した形で組み立てられることです。

これらの条件が成り立たないなら、過去の結果を保存しても、メモリを余分に使うだけであまり効果がないことがあります。

メモ化とタブulationの違い

メモ化：トップダウンで保存する

メモ化は、まず再帰の考え方から始めます。アルゴリズムがある部分問題を初めて解いたとき、その結果を保存します。以後は再計算せず、保存した値を使い回します。

この方法は、漸化式ははっきりしているが、必要な状態をどの順番で求めるかが見えにくいときによく使いやすいです。

タブulation：ボトムアップで構築する

タブulationは、ベースケースから始めて、必要な依存関係が先にそろう順番で状態を埋めていきます。

この方法は、きれいな反復順序がすでに分かっていて、表の埋め方を明示的に制御したいときに使いやすいです。

動的計画法の例：フィボナッチ数列

フィボナッチ数列は次のように定義されます。

$$F(0) = 0, \quad F(1) = 1$$

そして、$n \ge 2$ のとき、

$$F(n) = F(n-1) + F(n-2)$$

単純な再帰解法では、同じ計算を何度も繰り返します。たとえば $F(5)$ を計算するには $F(4)$ と $F(3)$ が必要で、さらに $F(4)$ を計算するときにもまた $F(3)$ が必要です。このような重複した $F(3)$ の計算こそ、動的計画法が取り除く無駄です。

フィボナッチでのメモ化

メモ化では、漸化式そのものは変わりませんが、各値を最初に計算した時点で保存します。

$F(5)$ では、役に立つ流れは次のようになります。

• $F(0)=0$ を計算して保存する
• $F(1)=1$ を計算して保存する
• $F(2)=1$ を計算して保存する
• $F(3)=2$ を計算して保存する
• $F(4)=3$ を計算して保存する
• $F(5)=5$ を計算して保存する

重要なのは、各状態が1回だけ計算されることです。その後の要求では、保存済みの値を読むだけで済みます。

フィボナッチでのタブulation

タブulationでは、ベースケースから上に向かって構築します。

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

この方法では依存関係の順序がはっきり見えます。新しい値はどれも、すでに分かっている値だけを使って求められます。

なぜ動的計画法は高速になることがあるのか

問題において重要な異なる状態が $k$ 個しかないなら、動的計画法はその $k$ 個の状態をそれぞれ1回ずつ解こうとします。すると、大きな再帰木が、はるかに小さな計算に置き換わることがあります。

どれだけ速くなるかは問題によって異なります。動的計画法だからといって自動的に高速になるわけではありません。元の解法で重複計算が本当に起きているときに効果を発揮します。

動的計画法でよくある間違い

部分問題が重複しないのに使ってしまう

すべての再帰問題が動的計画法の問題とは限りません。ほとんどの部分問題が毎回異なるなら、結果をキャッシュしても十分な効果が出ないことがあります。

状態の定義を間違える

状態には、次のステップに必要な情報をすべて含める必要があります。重要な情報が欠けていると、漸化式が正しそうに見えても、答えは間違ってしまいます。

ベースケースを間違える

ベースケースは方法全体の土台です。初期値が間違っていれば、そこから作られる後続の状態もすべて間違います。

表を埋める順序を間違える

タブulationは、各状態が依存先の状態より後に埋められるときにだけ正しく機能します。漸化式が正しくても、埋める順序が間違っていれば失敗します。

動的計画法は常に最適化問題だと思い込む

有名な例には最大化や最小化の問題が多いですが、動的計画法は数え上げ問題や判定問題にも使われます。本当の目印は「最良」という言葉ではなく、再利用できる部分問題があることです。

動的計画法はどこで使われるか

動的計画法は、編集距離、最長共通部分列、経路数の数え上げ、ナップサック型の最適化、一部の最短経路問題などで登場します。

使うべきかどうかを考えるときは、次の2つを自分に問いかけてください。

• 小さな部分問題は繰り返し現れるか？
• 大きな答えはそれらの小さな答えから組み立てられるか？

両方が yes なら、動的計画法は有力な候補です。

似た問題に挑戦してみよう

1回の移動で $1$ 段または $2$ 段進めるとして、$n$ 段の階段を上る方法の数を自分で考えてみましょう。漸化式はシンプルで、重複する部分問題も見つけやすく、フィボナッチの次に学ぶ例としてちょうどよい問題です。