Day 10: 動的計画法と貪欲法
今日学ぶこと
- 動的計画法（DP）の基本概念
- トップダウン（メモ化）とボトムアップ（表）
- 貪欲法の考え方
- 動的計画法と貪欲法の使い分け
動的計画法（Dynamic Programming）
動的計画法（DP） は、問題を重複する部分問題に分解し、各部分問題を一度だけ解いて結果を保存することで効率化する手法です。
flowchart TB
subgraph NaiveRecursion["素朴な再帰（重複あり）"]
F5["fib(5)"] --> F4["fib(4)"]
F5 --> F3a["fib(3)"]
F4 --> F3b["fib(3)"]
F4 --> F2a["fib(2)"]
F3a --> F2b["fib(2)"]
F3a --> F1a["fib(1)"]
F3b --> F2c["fib(2)"]
F3b --> F1b["fib(1)"]
end
style F3a fill:#ef4444,color:#fff
style F3b fill:#ef4444,color:#fff
style F2a fill:#f59e0b,color:#fff
style F2b fill:#f59e0b,color:#fff
style F2c fill:#f59e0b,color:#fff
DPが使える条件
- 重複する部分問題: 同じ計算が何度も行われる
- 最適部分構造: 部分問題の最適解を組み合わせて全体の最適解を得られる
トップダウン（メモ化）
再帰 + キャッシュで実装します。
// Fibonacci with memoization: O(n) time, O(n) space
function fibMemo(n, memo = new Map()) {
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;
}
console.log(fibMemo(50)); // 12586269025
ボトムアップ（表）
小さい部分問題から順に解いて表を埋めます。
// Fibonacci bottom-up: O(n) time, O(n) space
function fibTable(n) {
if (n <= 1) return n;
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Space-optimized: O(n) time, O(1) space
function fibOptimized(n) {
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問題
1. 階段の上り方（Climbing Stairs）
n段の階段を1段または2段ずつ上る方法の数。
function climbStairs(n) {
if (n <= 2) return n;
const dp = [0, 1, 2];
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
console.log(climbStairs(5)); // 8
2. コイン問題（Coin Change）
最小のコイン枚数で目標金額を作る。
function coinChange(coins, amount) {
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 - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
console.log(coinChange([1, 5, 10, 25], 36)); // 3 (25 + 10 + 1)
console.log(coinChange([2], 3)); // -1
flowchart LR
subgraph DP["dp配列（coins=[1,5,10]、amount=11）"]
D0["dp[0]\n0"]
D1["dp[1]\n1"]
D5["dp[5]\n1"]
D10["dp[10]\n1"]
D11["dp[11]\n2"]
end
D0 -->|"+1"| D1
D0 -->|"+5"| D5
D0 -->|"+10"| D10
D10 -->|"+1"| D11
style D0 fill:#22c55e,color:#fff
style D11 fill:#3b82f6,color:#fff
3. 最長共通部分列（LCS）
function longestCommonSubsequence(text1, text2) {
const m = text1.length;
const n = text2.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
console.log(longestCommonSubsequence("abcde", "ace")); // 3 ("ace")
4. ナップサック問題（0/1 Knapsack）
function knapsack(weights, values, capacity) {
const n = weights.length;
const dp = Array.from({ length: n + 1 }, () =>
new Array(capacity + 1).fill(0)
);
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(
dp[i - 1][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]
);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
console.log(knapsack(weights, values, 8)); // 10
5. 最長増加部分列（LIS）
function lengthOfLIS(nums) {
const dp = new Array(nums.length).fill(1);
for (let i = 1; i < nums.length; 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);
}
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4 ([2,5,7,101])
貪欲法（Greedy Algorithm）
貪欲法は、各ステップで局所的に最適な選択をすることで、全体として最適な解を得る手法です。
flowchart TB
subgraph Greedy["貪欲法の考え方"]
S["問題"] --> C1["選択1\n（最良を選ぶ）"]
C1 --> C2["選択2\n（最良を選ぶ）"]
C2 --> C3["選択3\n（最良を選ぶ）"]
C3 --> R["解"]
end
style Greedy fill:#22c55e,color:#fff
貪欲法が有効な条件
- 貪欲選択性質: 局所最適解が全体最適解に含まれる
- 最適部分構造: 部分問題の最適解が全体の最適解に寄与する
貪欲法の例
1. お釣りの最小枚数
function minCoinsGreedy(coins, amount) {
// Sort coins in descending order
coins.sort((a, b) => b - a);
let count = 0;
const used = [];
for (const coin of coins) {
while (amount >= coin) {
amount -= coin;
count++;
used.push(coin);
}
}
return amount === 0 ? { count, used } : null;
}
console.log(minCoinsGreedy([1, 5, 10, 25], 36));
// { count: 3, used: [25, 10, 1] }
注意: 貪欲法は全てのコインの組み合わせで最適解を保証しません。例えば [1, 3, 4] で6を作る場合、貪欲法は 4+1+1=3枚 を返しますが、最適解は 3+3=2枚 です。
2. 区間スケジューリング
重ならない活動を最大数選ぶ。
function activitySelection(activities) {
// Sort by end time
activities.sort((a, b) => a.end - b.end);
const selected = [activities[0]];
let lastEnd = activities[0].end;
for (let i = 1; i < activities.length; i++) {
if (activities[i].start >= lastEnd) {
selected.push(activities[i]);
lastEnd = activities[i].end;
}
}
return selected;
}
const activities = [
{ name: "A", start: 1, end: 4 },
{ name: "B", start: 3, end: 5 },
{ name: "C", start: 0, end: 6 },
{ name: "D", start: 5, end: 7 },
{ name: "E", start: 3, end: 9 },
{ name: "F", start: 5, end: 9 },
{ name: "G", start: 6, end: 10 },
{ name: "H", start: 8, end: 11 },
];
console.log(activitySelection(activities));
// [A, D, H] — 3 activities
3. フラクショナルナップサック
function fractionalKnapsack(items, capacity) {
// Sort by value/weight ratio (descending)
items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
let totalValue = 0;
let remaining = capacity;
for (const item of items) {
if (remaining <= 0) break;
const take = Math.min(item.weight, remaining);
totalValue += (take / item.weight) * item.value;
remaining -= take;
}
return totalValue;
}
const items = [
{ weight: 10, value: 60 },
{ weight: 20, value: 100 },
{ weight: 30, value: 120 },
];
console.log(fractionalKnapsack(items, 50)); // 240
動的計画法 vs 貪欲法
| 特徴 | 動的計画法 | 貪欲法 |
|---|---|---|
| アプローチ | 全部分問題を解く | 局所最適を選ぶ |
| 最適性 | 常に最適解を保証 | 保証されない場合あり |
| 計算量 | 通常は高い | 通常は低い |
| 実装 | テーブル/メモ化 | シンプルなループ |
| 例 | 0/1ナップサック、LCS | 区間スケジューリング、お釣り |
flowchart TB
Q1{"問題に最適部分構造\nがある？"}
Q1 -->|No| BF["全探索"]
Q1 -->|Yes| Q2{"貪欲選択性質\nがある？"}
Q2 -->|Yes| G["貪欲法"]
Q2 -->|No| Q3{"重複する\n部分問題がある？"}
Q3 -->|Yes| DP["動的計画法"]
Q3 -->|No| DC["分割統治法"]
style G fill:#22c55e,color:#fff
style DP fill:#3b82f6,color:#fff
style DC fill:#8b5cf6,color:#fff
style BF fill:#ef4444,color:#fff
DPの解法テンプレート
// 1. Define state: dp[i] = ...
// 2. Define transition: dp[i] = f(dp[i-1], ...)
// 3. Define base case: dp[0] = ...
// 4. Define answer: dp[n] or max(dp)
function dpTemplate(input) {
const n = input.length;
// Step 1 & 3: Initialize dp with base cases
const dp = new Array(n).fill(0);
dp[0] = /* base case */;
// Step 2: Fill dp table
for (let i = 1; i < n; i++) {
dp[i] = /* transition using dp[0..i-1] */;
}
// Step 4: Return answer
return dp[n - 1]; // or Math.max(...dp)
}
まとめ
| 概念 | 説明 |
|---|---|
| 動的計画法 | 部分問題の結果を保存して再利用する手法 |
| メモ化 | トップダウンDP、再帰+キャッシュ |
| ボトムアップ | テーブルを小さい問題から埋めるDP |
| 貪欲法 | 各ステップで局所最適を選ぶ手法 |
| 最適部分構造 | 部分問題の最適解で全体の最適解が構成できる性質 |
重要ポイント
- DPは「重複する部分問題」と「最適部分構造」の両方が必要
- ボトムアップは再帰スタックを使わず、空間最適化がしやすい
- 貪欲法はDPより効率的だが、適用できる問題が限られる
- 問題を見極めて適切な手法を選ぶことが重要
練習問題
問題1: 基本
与えられた硬貨の種類と金額に対して、その金額を作る方法の数を求める関数を実装してください（DPを使用）。
問題2: 応用
m×n のグリッドの左上から右下までの経路の数を求めてください（右か下にのみ移動可能）。
チャレンジ問題
文字列の最小編集距離（レーベンシュタイン距離）を求める関数を実装してください。許可される操作は挿入、削除、置換の3つです。
参考リンク
おめでとうございます！ 10日間のデータ構造とアルゴリズムの学習を完了しました。ここで学んだ知識を基に、LeetCodeやAtCoderなどのプラットフォームで実践を重ねていきましょう。