動的計画法 — 同じ計算を二度しない

素直に書いた再帰が、入力を少し増やしただけで返ってこなくなる。この現象には決まった原因があります。同じ引数の計算を、何度も繰り返しているのです。

動的計画法は、その繰り返しを 1 回に潰す技法です。難しい名前が付いていますが、やっていることは「一度計算した答えを覚えておく」だけです。

この章で学ぶこと

• 部分問題の重なりに気づく方法
• メモ化と表埋めの対応。どちらで書くか
• 適用できる 2 つの条件
• 計算量を状態数 × 遷移コストで見積もる
• 状態と遷移をどう設計するか

前提知識

再帰と分割統治 の再帰木と、計算量 の O 記法を前提にします。

重なりに気づく

再帰と分割統治の章で、フィボナッチを定義どおりに書くと fib(30) で 269 万回の呼び出しが起きることを見ました。

fib(3) が 2 回、fib(2) が 3 回現れています。引数が同じなら答えも同じなのに、その都度たどり直しています。

**この「同じ引数が再帰木に複数回現れる」状態を、部分問題の重なりと呼びます。**分割統治との違いはここです。マージソートでは、左半分と右半分は重なりません。だから覚えておく意味がありません。

メモ化 — 上から、覚えながら

答えを表に控え、2 回目からは表を引きます。再帰の形はそのままです。

let memoCalls = 0;
function fibMemo(n: number, memo = new Map<number, number>()): number {
  memoCalls++;
  if (n <= 1) return n;
  const hit = memo.get(n);
  if (hit !== undefined) return hit; // 2 回目はここで返る
  const v = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, v);
  return v;
}

memoCalls = 0;
fibMemo(30);
console.log(`メモ化した fib(30) の呼び出し回数: ${memoCalls}`);
// メモ化した fib(30) の呼び出し回数: 59

269 万回が 59 回になりました。n が 0 から 30 まで 31 種類あり、各引数について「初回の計算」と「表からの引き当て」が高々 1 回ずつ起きるだけだからです。

**指数から線形に落ちています。**アルゴリズムを変えたわけではなく、重なりを潰しただけです。

表埋め — 下から、順に

同じことを、再帰をやめて小さいほうから順に埋めても実現できます。

function fibTable(n: number): number {
  if (n <= 1) return n;
  const dp = new Array<number>(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

console.log(`fibTable(30) = ${fibTable(30)}`);
// fibTable(30) = 832040

2 つは同じものの裏表

	メモ化 (トップダウン)	表埋め (ボトムアップ)
書き方	再帰のまま。表を足す	ループで小さい順に埋める
計算する範囲	必要な部分問題だけ	表の全マス
スタック	深さぶん積まれる	積まれない
向いている場面	状態が広く、実際に使うのは一部	全部の状態を使う。順序が自明

**まずメモ化で書くのを勧めます。**素直な再帰に 3 行足すだけででき、遷移の式が定義そのままの形で残るので間違えにくいからです。深さが問題になったとき、または全状態を使うと分かったときに表埋めへ書き換えます。

使える条件は 2 つ

条件	意味	満たさない例
部分問題の重なり	同じ部分問題が何度も現れる	マージソート (左右は別のデータ)
最適部分構造	部分問題の最適解を組み合わせると全体の最適解になる	部分の選択が後の選択肢を変えてしまう問題

重なりが無ければ覚える意味がなく、最適部分構造が無ければ組み立てた答えが最適になりません。どちらか一方だけでは動的計画法になりません。

計算量は「状態数 × 遷移コスト」

動的計画法の計算量は、この掛け算で出ます。

• 状態数 = 表のマス目の数
• 遷移コスト = 1 マスを埋めるのに見る他のマスの数

フィボナッチなら状態数が n、1 マスにつき 2 マス見るので O(n)。後で出てくる 2 次元の例なら状態数が n × m、1 マスにつき定数マスなので O(n × m) です。

**この見積もりは設計の指針になります。**状態を 1 つ増やすと表が次元ごと増えるので、状態の持ちすぎは計算量に直結します。「この情報は本当に状態に要るか」を先に絞ってください。

状態と遷移を設計する

階段を 1 段または 2 段ずつ登るとき、n 段目までの登り方が何通りあるかを考えます。

設計は 3 つを決めることです。

1. 状態 — dp[i] = i 段目に到達する登り方の数
2. 遷移 — i 段目へは i-1 段目から 1 段、i-2 段目から 2 段で来る。つまり dp[i] = dp[i-1] + dp[i-2]
3. 初期値 — dp[0] = 1 (何もしないのが 1 通り)

function climbWays(n: number): number {
  const dp = new Array<number>(n + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= n; i++) {
    dp[i] = dp[i - 1] + (i >= 2 ? dp[i - 2] : 0);
  }
  return dp[n];
}

console.log(`climbWays(5) = ${climbWays(5)}`);   // climbWays(5) = 8
console.log(`climbWays(10) = ${climbWays(10)}`); // climbWays(10) = 89

遷移は「今の状態にどこから来られるか」で書きます。「どこへ行けるか」で書いても同じ表が埋まりますが、来る側で書くほうが初期値の置き場所が明確になります。

表が 2 次元になる例

2 つの文字列に共通して現れる、連続とは限らない最も長い並び — 最長共通部分列を求めます。差分表示の土台になっている計算です。

• 状態 — dp[i][j] = a の先頭 i 文字と b の先頭 j 文字での答え
• 遷移 — 末尾の文字が一致するなら dp[i-1][j-1] + 1、しないなら「a の末尾を捨てる」「b の末尾を捨てる」の大きいほう

function lcsLength(a: string, b: string): number {
  const dp: number[][] = Array.from({ length: a.length + 1 }, () =>
    new Array<number>(b.length + 1).fill(0),
  );
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      dp[i][j] = a[i - 1] === b[j - 1]
        ? dp[i - 1][j - 1] + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[a.length][b.length];
}

console.log(lcsLength("abcde", "ace"));      // 3
console.log(lcsLength("kitten", "sitting")); // 4

状態数が n × m、遷移が定数なので O(n × m) です。

直前の行だけ持つ

上のコードで dp[i][j] が見るのは dp[i-1][*] と dp[i][j-1] だけです。2 行ぶんあれば足ります。

function lcsLengthTwoRows(a: string, b: string): number {
  let prev = new Array<number>(b.length + 1).fill(0);
  for (let i = 1; i <= a.length; i++) {
    const cur = new Array<number>(b.length + 1).fill(0);
    for (let j = 1; j <= b.length; j++) {
      cur[j] = a[i - 1] === b[j - 1]
        ? prev[j - 1] + 1
        : Math.max(prev[j], cur[j - 1]);
    }
    prev = cur;
  }
  return prev[b.length];
}

空間が O(n × m) から O(m) に落ちます。時間は変わりません。

代償があります。この 2 行版では経路を復元できません。「長さ」だけでなく「実際にどの文字が共通か」が要るなら、表を全部残すのが素直です。差分表示は経路の復元が目的なので、素朴に圧縮すると使えなくなります。(分割統治と組み合わせて線形の空間で復元する手法もありますが、実装は重くなります。)

貪欲法との違い

貪欲法は、その場で最も良く見える選択をして、後戻りしません。動くときは動的計画法より速く、コードも短くなります。

分かれ目は局所的な最適を選び続けて全体の最適に届くかです。届く問題では貪欲法が正しく、届かない問題では動的計画法が要ります。

硬貨で釣り銭を作る問題が分かりやすい例です。日本の硬貨 (1・5・10・50・100・500 円) なら、大きいほうから貪欲に取れば最小枚数になります。しかし硬貨が 1・3・4 円だとして 6 円を作るとき、貪欲だと 4 + 1 + 1 で 3 枚ですが、最適は 3 + 3 の 2 枚です。

**硬貨の種類という「入力」が変わると、貪欲法の正しさが崩れます。**貪欲法を採るなら「なぜこの問題では局所最適が全体最適になるか」を言えることが条件です。言えないなら動的計画法を選びます。

判断の手順

1. **素直に再帰で書く。**動く形を先に作る
2. 再帰木に同じ引数が現れるかを見る。現れなければ動的計画法の出番ではない
3. **メモ化する。**表を足すだけ
4. 状態数 × 遷移コストを数え、間に合うか確かめる
5. 深さが問題になるか全状態を使うなら表埋めへ書き換える
6. 空間が問題なら直前の行だけ持つ。ただし経路の復元が要るなら圧縮しない

**2 の判断が最も重要です。**動的計画法は「遅い再帰を速くする」道具ではありません。重なりがあるときだけ効きます。重なりが無いのに遅いなら、原因は別のところにあります。

よくある誤解

「動的計画法は難しいアルゴリズム」 — アルゴリズムではなく技法です。中身は「答えを表に控える」だけで、難しいのは状態と遷移の設計のほうです。

「メモ化と動的計画法は別物」 — メモ化は動的計画法の書き方の 1 つです。上から書くか下から書くかの違いで、埋まる表は同じです。

「表埋めのほうが速い」 — オーダーは同じです。表埋めは関数呼び出しが無いぶん定数倍で有利ですが、必要ない部分問題まで埋めてしまうぶん不利になることもあります。状態空間が広く、実際に使うのが一部なら、メモ化のほうが速く終わります。

「再帰が遅いからメモ化する」 — 遅い原因は再帰ではなく重なりです。重なりの無い再帰をメモ化しても、表を作るぶん遅くなります。

「状態は多く持つほうが安全」 — 状態を 1 つ足すと表が次元ごと増えます。状態数が計算量に直結するので、必要最小限まで削るのが設計です。

確認問題

問 1. 再帰で書いた処理が遅いのでメモ化しました。速くなりませんでした。何を確かめますか。

答え: 再帰木に同じ引数が複数回現れているかを確かめます。

メモ化が効くのは重なりがあるときだけです。効かなかったということは、次のどれかです。

• 重なりが無い — 分割統治のように、部分問題が互いに素な形。この場合メモ化は表を作るぶん遅くなる
• 引数がキーとして一致していない — オブジェクトや配列をそのままキーにすると、中身が同じでも別物として扱われる。文字列や数値に正規化する必要がある
• メモが呼び出しごとに作り直されている — 再帰のたびに新しい Map を渡していると、記録が引き継がれない

切り分けは呼び出し回数を数えることです。メモ化の前後で回数が変わらなければ、上の 2 つ目か 3 つ目です。回数は減ったのに時間が変わらないなら、1 回あたりの処理が重いということで、原因はメモ化の外にあります。

問 2. 予算内で商品の組合せを選ぶ処理 (いわゆるナップサック問題) を動的計画法で書いたら、メモリが足りなくなりました。状態は「何番目の商品まで見たか」「使った予算」「選んだ個数」の 3 つです。どうしますか。

答え: 状態を減らせないかを先に見ます。3 次元の表は、1 つ削るだけで桁が変わります。

状態数は 3 つの積です。商品 1,000 種類 × 予算 100 万 × 個数 100 なら 1,000 億マスで、どう書いても収まりません。

順に検討します。

1. 本当に要る状態か — 「選んだ個数」が答えの条件に入っていないなら削れる。制約を読み直す
2. 粒度を粗くできるか — 予算が円単位である必要はなく、100 円単位で足りるなら状態数が 100 分の 1 になる
3. 次元を落とせるか — 「何番目まで見たか」は多くの場合直前の 1 つ前しか参照しないので、2 行だけ持てば消せる

3 つ目が最も効きます。上の例なら 1,000 倍の削減です。ただし経路の復元ができなくなるので、「どの商品を選んだか」が答えに要るなら使えません。その場合は、選択を別の軽い形で記録するか、表を分割して段階的に処理します。

**設計を疑うのが先で、実装の工夫は後です。**状態が 3 つある時点で、問題の読み違いを疑う価値があります。

問 3. 「最短経路」を求める問題で、動的計画法と幅優先探索のどちらを使うか、どう判断しますか。

答え: 状態の遷移に閉路があるかどうかで決めます。

動的計画法は、部分問題に順序が付くことが前提です。dp[i] を計算するときに dp[i-1] が確定している、という関係が要ります。この順序が付くのは、状態の遷移が一方向に進むとき — つまり閉路が無いときです。

• 閉路が無い (段が進む一方、文字を消費していく) → 動的計画法。表を順に埋められる
• 閉路がある (同じ場所に戻れる盤面や地図) → 幅優先探索。順序が決まらないので表を埋められない

グラフと探索の章で見たトポロジカルソートは、この橋渡しです。閉路の無い有向グラフなら順序が決められるので、その順に表を埋めれば動的計画法として書けます。

**実際には両方が同じものを指していることもあります。**辺の重みが等しい閉路の無いグラフでは、BFS で得られる距離と動的計画法で埋めた表は一致します。どちらで書くかは、状態が自然に順序付くかどうかの読みやすさで選んでかまいません。

まとめ

• 動的計画法はアルゴリズムでなく技法。「一度計算した答えを覚えておく」だけ
• 効くのは部分問題の重なりがあるとき。再帰木に同じ引数が複数回現れるかで判定する
• **メモ化 (上から) と表埋め (下から) は同じものの裏表。**まずメモ化で書く
• 適用条件は重なりと最適部分構造の 2 つ。片方だけでは成り立たない
• 計算量は状態数 × 遷移コスト。状態を 1 つ増やすと表が次元ごと増える
• 設計は状態・遷移・初期値の 3 つを決めること。遷移は「どこから来るか」で書く
• **直前の行だけ持てば空間が 1 次元ぶん落ちる。**ただし経路の復元はできなくなる
• 貪欲法との分かれ目は局所最適が全体最適に届くか。届く理由を言えないなら動的計画法
• **遅い再帰を何でも速くする道具ではない。**重なりが無ければ効かない

関連リファレンス

• 計算量 — 状態数 × 遷移コストを見積もる土台
• 二分探索 — 分割統治で「片方しか解かない」形。重なりが無いので表を持つ意味がない対比

次に読む

• 配列を走査する型 — 表を作らずに二重ループを一重に落とす別の道具
• 再帰と分割統治 — 重なりの無い再帰との対比