動的計画法

動的計画法とは

動的計画法 (Dynamic Programming, DP) は、問題を重複する部分問題に分割し、各部分問題の結果をメモ化 (キャッシュ) して重複計算を排除するアルゴリズム設計手法である。再帰的な解法の指数的な計算量を多項式時間に削減する。

フィボナッチ数列の例

// ❌ 素朴な再帰: O(2^n) - 同じ計算を何度も繰り返す
function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// ✅ メモ化 (トップダウン): O(n)
function fibMemo(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

// ✅ テーブル (ボトムアップ): O(n)、スタックオーバーフローなし
function fibDP(n: number): number {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) [prev, curr] = [curr, prev + curr];
  return curr;
}

トップダウン vs ボトムアップ

アプローチ	方法	メリット
トップダウン (メモ化)	再帰 + キャッシュ	直感的、必要な部分問題のみ計算
ボトムアップ (テーブル)	ループ + 配列	スタックオーバーフローなし

DP が適用できる条件

DP が適用できるのは、最適解が部分問題の最適解から構成される「最適部分構造」と、同じ部分問題が複数回出現する「重複部分問題」の 2 つの条件を満たす場合だ。

代表的な DP 問題

問題	説明
ナップサック問題	容量制限内で価値を最大化
最長共通部分列 (LCS)	2 つの文字列の共通部分列
コイン問題	最小枚数で金額を作る
編集距離	文字列の変換に必要な最小操作数

コイン問題

// 金額 amount を作るのに必要な最小コイン枚数
function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

coinChange([1, 5, 10], 13); // 4 (10 + 1 + 1 + 1)

実務での DP

コーディング面接では頻出だが、実務で DP を直接書く機会は少ない。ただし、キャッシュ (メモ化) の考え方は API レスポンスのキャッシュ、計算結果のキャッシュなど広く応用される。

実践的な知識は関連書籍でも得られる。