動的計画法（DP）入門 — 「表を埋める」だけと考える

**動的計画法（DP: Dynamic Programming）**は、コーディングテスト界で「初心者殺し」と呼ばれる壁です。しかし正体は恐ろしいものではありません。一言でいえば——

小さい問題の答えを表に書き溜めて、大きい問題の答えを組み立てる。

それだけです。「動的」も「計画」も歴史的な命名の綾で、実態は「表埋め」。この章では3つの定番問題を同じ手順で解き、DPを「型」に落とします。

ウォームアップ: 階段の上り方

問題: N段の階段を、1歩で1段または2段上れる。上り方は何通りあるか。（N ≤ 50）

全探索なら2^N通りの上り方を列挙することになりますが、視点を変えます。「N段目に着く直前、どこにいたか？」——N-1段目かN-2段目のどちらかしかありません。つまり:

N段目への上り方 = (N-1段目への上り方) + (N-2段目への上り方)

小さい問題（N-1、N-2）の答えから大きい問題（N）の答えが作れる。ならば小さい順に表を埋めればいい、というのがDPです。

function countWays(n: number): number {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;                    // 「0段目にいる」状態は1通り（スタート）
  for (let i = 1; i <= n; i++) {
    dp[i] = dp[i - 1] + (i >= 2 ? dp[i - 2] : 0);
  }
  return dp[n];
}

O(N)。2^N通りの列挙が、表を1周埋めるだけになりました。第7章で予告した「全探索の重複計算を、記録で消す」の実演です。

DPを設計する3ステップ

いまの問題を解いた手順を、汎用の型にします。すべてのDPはこの3つを決めれば書けます。

1. 表の定義 — dp[i] は何を意味するか。日本語で言い切れること（例:「dp[i] = i段目への上り方の総数」）
2. 遷移 — dp[i] を、より小さい添字の値からどう作るか
3. 初期値 — 一番小さい問題の答え(スタート地点)

学習者

3ステップの中だと、どれが一番むずかしいの？

圧倒的に①表の定義です。遷移と初期値は、定義が正しければ半自動的に決まります。逆にDPで詰まるときはほぼ「dp[i]が何なのか自分で説明できていない」状態です。だから本書では、コードより先に必ず定義を日本語で書きます。

定番1: ナップサック問題

DPの王様です。前章で「貪欲では解けない」と宣告した問題を回収します。

問題: N個の品物（重さw、価値v）から、重さの合計W以下で価値の合計を最大化せよ。（N ≤ 100、W ≤ 10^5）

• 定義: dp[i][j] = 品物iまで検討して、重さjまで使えるときの最大価値
• 遷移: 品物iを「入れない」か「入れる」かの良い方
  • 入れない: dp[i-1][j]
  • 入れる: dp[i-1][j - w[i]] + v[i]（jがw[i]以上のときだけ）
• 初期値: dp[0][*] = 0（品物を検討する前の価値は0）

function knapsack(items: { w: number; v: number }[], W: number): number {
  const n = items.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    const { w, v } = items[i - 1];
    for (let j = 0; j <= W; j++) {
      dp[i][j] = dp[i - 1][j];                              // 入れない
      if (j >= w) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w] + v);  // 入れる
    }
  }
  return dp[n][W];
}

計算量はO(NW) = 100 × 10^5 = 10^7で余裕です。「選ぶ/選ばない × 容量制限 × 最大化」の三点セットが来たらナップサックDP。bit全探索(2^N)ではNが大きすぎるときの受け皿でもあります。

定番2: 最長増加部分列（LIS）

問題: 数列から、左から右へ「増加していく」ように要素を選ぶとき、最長の長さを求めよ。（例: [3, 1, 4, 1, 5, 9, 2, 6] → [1, 4, 5, 9] などで長さ4）

• 定義: dp[i] = i番目の要素で終わる増加部分列の最長の長さ
• 遷移: iより前のjで nums[j] < nums[i] なものの中から、最大の dp[j] + 1
• 初期値: すべて1（自分だけの列）

function lis(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(1);
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  return Math.max(...dp);
}

O(N²)なのでN ≤ 3,000程度まで。ポイントは定義の「i番目で終わる」という縛りです。この縛りがあるから遷移が素直に書ける——「〇〇で終わる」と定義するのはDPの頻出テクニックです。

なお、LISは二分探索（第8章のlowerBound）と組み合わせるとO(N log N)に改善できます。まずはO(N²)版を確実に書けることが先決です。

DPと気づくためのシグナル

DP最大の難所は「これはDPだ」と気づくことです。次のシグナルが2つ以上重なったらDPを疑ってください。

メンター

DPは「1問理解する」より「同じ問題を3回、白紙から書く」ほうが効きます。階段・ナップサック・LISの3問を、定義から自力で再構築できるようになったら、DP入門は卒業です。類題はACできなくても定義を言語化する練習だけで力がつきますよ。

この章のパターンの見分け方

まとめ

• DPの正体は「小さい問題の答えの表埋め」。全探索の重複計算を記録で消す技術
• 設計は3ステップ: ①dp[i]の日本語定義 → ②遷移 → ③初期値。詰まったら必ず①に戻る
• ナップサック=「選ぶ/選ばない×容量×最大化」、LIS=「i番目で終わる」定義が鍵
• 「何通り」「貪欲に反例」「N > 20の選択問題」はDPのシグナル
• デバッグは小さい入力で表を手書き・出力して目視

次章はPart 3の最終章、グラフの応用です。辺に重みがついた最短路（ダイクストラ法)と、つながりを高速管理するUnion-Findを道具箱に加えます。