動的計画法とグリーディ法の使い分け - DP・貪欲法・グラフ探索
📚 概要
コーディングテストの中級~上級問題では、動的計画法（DP）、グリーディ法（貪欲法）、グラフ探索が頻出します。これらは一見似ているように見えますが、適用条件が異なり、誤った手法を選ぶと正解にたどり着けません。
この記事では、DP とグリーディの本質的な違い、代表的な DP パターン（ナップサック、コイン問題、編集距離、最長増加部分列）、グラフ探索アルゴリズム（BFS/DFS、ダイクストラ、トポロジカルソート）、そしてバックトラッキングまでを体系的に解説します。
🕰️ 歴史的背景
動的計画法の誕生
動的計画法は 1950年代 に数学者 Richard Bellman によって命名されました。「Dynamic Programming」という名前は、当時の国防省で「プログラミング」が良い印象を持たれていたため、研究に予算をつけやすくする意図もあったと Bellman 本人が述べています。
グリーディ法の形式化
グリーディアルゴリズムの理論的基盤は、1971年 に Jack Edmonds のマトロイド理論によって確立されました。「局所的に最適な選択を繰り返せば大域的に最適になる」という条件が数学的に明確化されました。
グラフアルゴリズムの発展
- 1956年: ダイクストラ法（Edsger Dijkstra）
- 1958年: Bellman-Ford 法
- 1962年: Floyd-Warshall 法
- 1972年: Tarjan の強連結成分分解
- 現在: これらのアルゴリズムは経路探索、ネットワーク最適化、SNS 分析など広範に応用
🔧 技術解説
1. 動的計画法（DP）
DP が適用できる2つの条件
graph TB
A["問題に DP を適用できるか?"] --> B{"最適部分構造?"}
B -->|No| C["DP は使えない"]
B -->|Yes| D{"部分問題の重なり?"}
D -->|No| E["分割統治法
(マージソートなど)"]
D -->|Yes| F["DP が有効!"]
style C fill:#ff6b6b
style E fill:#ffa94d
style F fill:#51cf66- 最適部分構造（Optimal Substructure）: 問題全体の最適解が、部分問題の最適解から構成できる
- 部分問題の重なり（Overlapping Subproblems）: 同じ部分問題が何度も繰り返し登場する
DP の2つのアプローチ
| アプローチ | 方向 | 実装方法 | 特徴 |
|---|---|---|---|
| トップダウン（メモ化再帰） | 大→小 | 再帰 + メモ化テーブル | 直感的、必要な部分だけ計算 |
| ボトムアップ（漸化式） | 小→大 | ループ + テーブル | 再帰のオーバーヘッドなし |
パターン1: フィボナッチ数列（DP 入門）
// 素朴な再帰: O(2^n) — 指数時間で非常に遅い
function fib_naive(n):
if n <= 1: return n
return fib_naive(n - 1) + fib_naive(n - 2)
graph TB
A["fib(5)"] --> B["fib(4)"]
A --> C["fib(3)"]
B --> D["fib(3)"]
B --> E["fib(2)"]
C --> F["fib(2)"]
C --> G["fib(1)"]
D --> H["fib(2)"]
D --> I["fib(1)"]
style D fill:#ff6b6b
style F fill:#ff6b6b
style H fill:#ff6b6bfib(3) が2回、fib(2) が3回計算されている（部分問題の重なり）。
// トップダウン（メモ化再帰）: O(n)
function fib_memo(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
// ボトムアップ（漸化式）: O(n) 時間, O(n) 空間
function fib_dp(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
// ボトムアップ（空間最適化）: O(n) 時間, O(1) 空間
function fib_optimized(n):
if n <= 1: return n
prev2 = 0
prev1 = 1
for i in range(2, n + 1):
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
return prev1
パターン2: ナップサック問題
重さと価値を持つ N 個のアイテムから、重さ制限 W 以内で価値を最大化する。
0-1 ナップサック（各アイテムは1回だけ使用可能）
// dp[i][w] = 最初の i 個のアイテムで、重さ上限 w の場合の最大価値
function knapsack_01(weights, values, W):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
// アイテム i を入れない場合
dp[i][w] = dp[i - 1][w]
// アイテム i を入れる場合
if weights[i - 1] <= w:
dp[i][w] = max(dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1])
return dp[n][W]
graph TB
A["アイテム: (重さ, 価値)
A(2, 3), B(3, 4), C(4, 5), D(5, 6)
重さ上限: 7"] --> B["dp テーブルを埋める"]
B --> C["dp[4][7] = 9
アイテム A(3) + D(6) = 9"]
style C fill:#51cf66無制限ナップサック（各アイテムを何回でも使用可能）
// dp[w] = 重さ上限 w の場合の最大価値
function knapsack_unbounded(weights, values, W):
dp = [0] * (W + 1)
for w in range(1, W + 1):
for i in range(len(weights)):
if weights[i] <= w:
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
| ナップサック | 遷移元 | 遷移式 | 計算量 |
|---|---|---|---|
| 0-1 | dp[i-1][w] | dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi) | O(nW) |
| 無制限 | dp[w] | dp[w] = max(dp[w-wi] + vi) for all i | O(nW) |
パターン3: コイン問題
与えられた種類のコインで金額 amount を作るための最小枚数を求める。
// dp[i] = 金額 i を作るための最小コイン枚数
function coin_change(coins, amount):
dp = [infinity] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
return dp[amount] if dp[amount] != infinity else -1
// 例: coins = [1, 5, 10], amount = 13
// dp[0]=0, dp[1]=1, ..., dp[5]=1, ..., dp[10]=1, dp[11]=2, dp[12]=3, dp[13]=3
// 答え: 3 (10 + 1 + 1 + 1 ではなく 10 + 1 + 1 + 1 = 3枚)
// 修正: 答え: 3枚 (5 + 5 + 1 + 1 + 1 = 5枚ではなく 10 + 1 + 1 + 1 = 4枚でもなく)
// 正解: coins=[1,5,10], amount=13 → 10+1+1+1 = 4枚
パターン4: 編集距離（Levenshtein Distance）
2つの文字列を一致させるために必要な操作（挿入、削除、置換）の最小回数。
// dp[i][j] = s1[0..i) と s2[0..j) の編集距離
function edit_distance(s1, s2):
m = len(s1)
n = len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
// ベースケース
for i in range(m + 1):
dp[i][0] = i // s1 の最初の i 文字を全削除
for j in range(n + 1):
dp[0][j] = j // s2 の最初の j 文字を全挿入
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] // 一致、コスト0
else:
dp[i][j] = 1 + min(
dp[i - 1][j], // 削除
dp[i][j - 1], // 挿入
dp[i - 1][j - 1] // 置換
)
return dp[m][n]
graph LR
A["'kitten'"] --> B["sitten
(k→s 置換)"]
B --> C["sittin
(e→i 置換)"]
C --> D["sitting
(末尾に g 挿入)"]
style A fill:#ff6b6b
style D fill:#51cf66edit_distance("kitten", "sitting") = 3
パターン5: グリッド上の経路数
左上から右下まで、右か下にしか移動できない場合の経路数。
// dp[i][j] = (0,0) から (i,j) までの経路数
function unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
// 障害物がある場合
function unique_paths_with_obstacles(grid):
m = len(grid)
n = len(grid[0])
dp = [[0] * n for _ in range(m)]
// 1行目
for j in range(n):
if grid[0][j] == 1: break // 障害物以降は到達不可
dp[0][j] = 1
// 1列目
for i in range(m):
if grid[i][0] == 1: break
dp[i][0] = 1
for i in range(1, m):
for j in range(1, n):
if grid[i][j] == 1:
dp[i][j] = 0 // 障害物
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
graph TB
subgraph Grid["3x3 グリッドの経路数"]
A["1"] --- B["1"] --- C["1"]
A --- D["1"] --- E["2"] --- F["3"]
D --- G["1"] --- H["3"] --- I["6"]
end
style I fill:#51cf66パターン6: 最長増加部分列（LIS）
// O(n^2) の DP 解法
// dp[i] = arr[i] で終わる LIS の長さ
function lis_dp(arr):
n = len(arr)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
// O(n log n) の二分探索解法
function lis_binary_search(arr):
tails = [] // tails[i] = 長さ i+1 の LIS の末尾の最小値
for x in arr:
pos = lower_bound(tails, x)
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)
// 例: arr = [10, 9, 2, 5, 3, 7, 101, 18]
// LIS: [2, 3, 7, 18] → 長さ 4
DP の空間最適化（ローリング配列）
2次元 DP テーブルで、遷移が「前の行」だけに依存する場合、1次元に圧縮できます。
// 0-1 ナップサック: O(nW) 空間 → O(W) 空間
function knapsack_optimized(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
// 後ろから走査（0-1 の場合）
for w in range(W, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
// 注意: 無制限ナップサックの場合は前から走査する
// 0-1 で後ろから走査する理由: 各アイテムを2回使うのを防ぐため
graph LR
A["2次元 DP
dp[i][w]
空間 O(nW)"] --> B["ローリング配列
dp[w]
空間 O(W)"]
style A fill:#ff8787
style B fill:#51cf662. グリーディ法（貪欲法）
グリーディが正しく動く条件
貪欲選択性質（Greedy Choice Property）: 各ステップで局所的に最適な選択をすれば、全体として最適解に到達できる。
graph TB
A["問題にグリーディを適用できるか?"] --> B{"貪欲選択性質?"}
B -->|No| C["DP を検討"]
B -->|Yes| D{"最適部分構造?"}
D -->|Yes| E["グリーディで解ける!"]
D -->|No| C
style C fill:#ffa94d
style E fill:#51cf66パターン1: 活動選択問題（区間スケジューリング）
終了時間が早い順に選ぶと、最大数の活動を実行できる。
// 終了時間でソートして、重ならない活動を貪欲に選ぶ
function activity_selection(activities):
// activities = [(start, end), ...]
sorted_acts = sort(activities, key=lambda x: x[1]) // 終了時間でソート
selected = [sorted_acts[0]]
last_end = sorted_acts[0][1]
for i in range(1, len(sorted_acts)):
start, end = sorted_acts[i]
if start >= last_end:
selected.append(sorted_acts[i])
last_end = end
return selected
// 例: [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)]
// 選択: (1,4), (5,7), (8,11), (12,16) → 4つ
gantt
title 区間スケジューリング
dateFormat X
axisFormat %s
section 選択
活動A (1-4) :done, 1, 4
活動D (5-7) :done, 5, 7
活動H (8-11) :done, 8, 11
活動K (12-16) :done, 12, 16
section 不選択
活動B (3-5) :crit, 3, 5
活動C (0-6) :crit, 0, 6
活動E (3-9) :crit, 3, 9パターン2: コイン問題（グリーディ版）
特定の硬貨体系（例: 1, 5, 10, 50, 100, 500 円）では、大きい額面から使うグリーディが最適。
// グリーディが正しい場合（日本の硬貨体系など）
function coin_greedy(coins, amount):
coins = sort(coins, reverse=True) // 大きい順
count = 0
for coin in coins:
count += amount // coin
amount = amount % coin
return count if amount == 0 else -1
// 注意: 任意のコインセットではグリーディは正しくない!
// 例: coins = [1, 3, 4], amount = 6
// グリーディ: 4 + 1 + 1 = 3枚
// 最適解: 3 + 3 = 2枚
// → DP が必要
パターン3: ハフマン符号化
頻度に基づく最適な可変長符号を構築する。
// 最も頻度の低い2つのノードを繰り返し結合
function huffman_coding(frequencies):
// 優先度付きキューを使用
heap = min_heap(frequencies)
while len(heap) > 1:
left = heap.pop() // 最小頻度
right = heap.pop() // 2番目に小さい頻度
merged = Node(left.freq + right.freq, left, right)
heap.push(merged)
return heap.pop() // ルートノード = ハフマン木
3. DP vs グリーディ vs 分割統治法
graph TB
A["最適化問題"] --> B{"部分問題の重なり?"}
B -->|Yes| C{"貪欲選択性質?"}
B -->|No| D["分割統治法"]
C -->|Yes| E["グリーディ法
O(n) or O(n log n)"]
C -->|No| F["動的計画法
O(nW), O(n²) etc."]
style D fill:#74c0fc
style E fill:#51cf66
style F fill:#ffa94d| 特性 | 動的計画法 (DP) | グリーディ法 | 分割統治法 |
|---|---|---|---|
| 戦略 | 全ての部分問題を解く | 局所最適を選ぶ | 分割して個別に解く |
| 最適性保証 | 常に最適 | 条件付きで最適 | 問題依存 |
| 部分問題の重なり | あり | あり | なし |
| 時間計算量 | 高め（テーブル全体） | 低め（1パス） | 問題依存 |
| 空間計算量 | テーブル分必要 | 通常 O(1) | 再帰スタック |
| 実装の難易度 | 中~高 | 低~中 | 中 |
| 代表例 | ナップサック、編集距離 | 区間スケジューリング | マージソート |
判断フローチャート:
- 問題に「最大」「最小」「最適」のキーワードがあるか? → 最適化問題
- 局所的な最適選択が全体の最適解を導くか? → グリーディ
- 同じ計算を何度もするか? → DP
- 部分問題が独立か? → 分割統治法
4. グラフ探索アルゴリズム
BFS と DFS の比較
graph TB
subgraph BFS_order["BFS: レベル順"]
B1["1"] --> B2["2"]
B1 --> B3["3"]
B2 --> B4["4"]
B2 --> B5["5"]
B3 --> B6["6"]
B3 --> B7["7"]
end
style B1 fill:#51cf66
style B2 fill:#74c0fc
style B3 fill:#74c0fc
style B4 fill:#ffa94d
style B5 fill:#ffa94d
style B6 fill:#ffa94d
style B7 fill:#ffa94dBFS 訪問順: 1 → 2, 3 → 4, 5, 6, 7
graph TB
subgraph DFS_order["DFS: 深さ優先"]
D1["1"] --> D2["2"]
D1 --> D3["3"]
D2 --> D4["4"]
D2 --> D5["5"]
D3 --> D6["6"]
D3 --> D7["7"]
end
style D1 fill:#51cf66
style D2 fill:#74c0fc
style D4 fill:#ffa94d
style D5 fill:#b197fc
style D3 fill:#ff8787
style D6 fill:#e599f7
style D7 fill:#ffe066DFS 訪問順: 1 → 2 → 4 → 5 → 3 → 6 → 7
島の数を数える（BFS/DFS の典型問題）
// グリッド上で連結した '1' の塊（島）の数を数える
function count_islands(grid):
if not grid:
return 0
rows = len(grid)
cols = len(grid[0])
count = 0
function dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != '1':
return
grid[r][c] = '0' // 訪問済みマーク
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count
トポロジカルソート
有向非巡回グラフ（DAG）のノードを、辺の方向に矛盾しない順序で並べる。
// カーンのアルゴリズム（BFS ベース）
function topological_sort(graph, num_nodes):
in_degree = [0] * num_nodes
for u in graph:
for v in graph[u]:
in_degree[v] += 1
queue = []
for i in range(num_nodes):
if in_degree[i] == 0:
queue.append(i)
result = []
while queue:
node = queue.pop(0)
result.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != num_nodes:
return None // サイクルが存在する
return result
graph LR
A["コンパイラ"] --> B["リンカ"]
C["テスト"] --> B
A --> D["テスト"]
E["ソースコード"] --> A
style E fill:#51cf66トポロジカル順序: ソースコード → コンパイラ → テスト → リンカ
最短経路アルゴリズムの比較
| アルゴリズム | ダイクストラ | Bellman-Ford | Floyd-Warshall |
|---|---|---|---|
| 用途 | 単一始点最短経路 | 単一始点最短経路 | 全頂点間最短経路 |
| 負の辺 | 不可 | 可能 | 可能 |
| 負の閉路検出 | 不可 | 可能 | 可能 |
| 計算量 | O((V+E) log V) | O(VE) | O(V^3) |
| データ構造 | 優先度付きキュー | 配列 | 2次元配列 |
| 適するケース | 辺の重みが非負 | 負の辺がある | 全ペアの距離が必要 |
ダイクストラ法
// 優先度付きキューを使ったダイクストラ法
function dijkstra(graph, start):
dist = {node: infinity for node in graph}
dist[start] = 0
pq = [(0, start)] // (距離, ノード)
while pq:
d, u = heappop(pq)
if d > dist[u]:
continue // より短い経路が既に見つかっている
for v, weight in graph[u]:
new_dist = dist[u] + weight
if new_dist < dist[v]:
dist[v] = new_dist
heappush(pq, (new_dist, v))
return dist
graph LR
A["A (0)"] -->|4| B["B (4)"]
A -->|1| C["C (1)"]
C -->|2| B
B -->|3| D["D (7)"]
C -->|5| D
C -->|8| E["E (9)"]
D -->|1| E
style A fill:#51cf66
style C fill:#74c0fc
style B fill:#74c0fc
style D fill:#ffa94d
style E fill:#ffa94dA→C(1) → C→B(3) → B→D(7) → D→E(8)
Bellman-Ford 法
// 負の辺にも対応できる単一始点最短経路
function bellman_ford(graph, start, num_nodes):
dist = [infinity] * num_nodes
dist[start] = 0
// V-1 回の緩和
for _ in range(num_nodes - 1):
for u, v, weight in all_edges:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
// 負の閉路チェック
for u, v, weight in all_edges:
if dist[u] + weight < dist[v]:
return None // 負の閉路が存在
return dist
Floyd-Warshall 法
// 全頂点間の最短距離を求める
function floyd_warshall(dist_matrix):
n = len(dist_matrix)
// dist_matrix[i][j] = 辺 (i, j) の重み。辺がなければ infinity
for k in range(n): // 経由点
for i in range(n): // 始点
for j in range(n): // 終点
if dist_matrix[i][k] + dist_matrix[k][j] < dist_matrix[i][j]:
dist_matrix[i][j] = dist_matrix[i][k] + dist_matrix[k][j]
return dist_matrix
5. バックトラッキング（枝刈り付き全探索）
解の候補を再帰的に構築し、条件を満たさない枝を早期に刈り取る（枝刈り）手法です。
graph TB
A["開始"] --> B["選択1"]
A --> C["選択2"]
A --> D["選択3"]
B --> E["選択1-1"]
B --> F["選択1-2 ✂️ 枝刈り"]
C --> G["選択2-1 ✂️ 枝刈り"]
C --> H["選択2-2"]
D --> I["選択3-1"]
H --> J["解発見!"]
style F fill:#ff6b6b
style G fill:#ff6b6b
style J fill:#51cf66// N-Queens: N x N のチェス盤に N 個のクイーンを互いに攻撃しないように配置
function solve_n_queens(n):
solutions = []
board = [-1] * n // board[row] = col
function is_safe(row, col):
for prev_row in range(row):
prev_col = board[prev_row]
// 同じ列 or 対角線上にクイーンがあるか
if prev_col == col or abs(prev_row - row) == abs(prev_col - col):
return False
return True
function backtrack(row):
if row == n:
solutions.append(board.copy())
return
for col in range(n):
if is_safe(row, col):
board[row] = col
backtrack(row + 1)
board[row] = -1 // バックトラック
backtrack(0)
return solutions
// 部分集合の列挙
function subsets(nums):
result = []
function backtrack(start, current):
result.append(current.copy())
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop() // バックトラック
backtrack(0, [])
return result
// subsets([1, 2, 3])
// → [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
💡 実践例
例題1: 最小コスト階段上り
階段の各段にコストがあり、1段か2段ずつ上れる。頂上に到達するための最小コストは?
function min_cost_climbing_stairs(cost):
n = len(cost)
dp = [0] * (n + 1)
for i in range(2, n + 1):
dp[i] = min(
dp[i - 1] + cost[i - 1],
dp[i - 2] + cost[i - 2]
)
return dp[n]
// 空間最適化版
function min_cost_optimized(cost):
prev2 = 0
prev1 = 0
for i in range(2, len(cost) + 1):
curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2])
prev2 = prev1
prev1 = curr
return prev1
例題2: 最大正方形
0 と 1 からなる2次元行列で、1 だけで構成される最大の正方形の面積を求める。
// dp[i][j] = (i, j) を右下隅とする最大正方形の辺の長さ
function maximal_square(matrix):
if not matrix:
return 0
m = len(matrix)
n = len(matrix[0])
dp = [[0] * n for _ in range(m)]
max_side = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
max_side = max(max_side, dp[i][j])
return max_side * max_side
例題3: 迷路の最短経路（BFS）
// グリッド上の (0,0) から (m-1, n-1) への最短経路（0が通路、1が壁）
function shortest_path(grid):
m = len(grid)
n = len(grid[0])
if grid[0][0] == 1 or grid[m-1][n-1] == 1:
return -1
queue = [(0, 0, 1)] // (行, 列, 距離)
visited = set()
visited.add((0, 0))
directions = [(0,1), (0,-1), (1,0), (-1,0)]
while queue:
r, c, dist = queue.pop(0)
if r == m - 1 and c == n - 1:
return dist
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 0 and (nr, nc) not in visited:
visited.add((nr, nc))
queue.append((nr, nc, dist + 1))
return -1 // 到達不可能
📊 DP パターン早見表
| パターン | 状態定義 | 遷移 | 計算量 | 典型問題 |
|---|---|---|---|---|
| 線形 DP | dp[i] | dp[i-1], dp[i-2] | O(n) | フィボナッチ、階段 |
| ナップサック | dp[i][w] | dp[i-1][w], dp[i-1][w-wi] | O(nW) | 0-1ナップサック |
| 区間 DP | dp[i][j] | dp[i][k] + dp[k][j] | O(n^3) | 行列積、回文分割 |
| 文字列 DP | dp[i][j] | dp[i-1][j-1] etc. | O(mn) | 編集距離、LCS |
| グリッド DP | dp[i][j] | dp[i-1][j], dp[i][j-1] | O(mn) | 経路数、最小コスト |
| ビット DP | dp[mask] | dp[mask ^ (1<<i)] | O(2^n * n) | 巡回セールスマン |
🎯 ベストプラクティス
1. DP の問題を解く手順
// ステップ1: 状態を定義する
// 「dp[i] は何を表すか?」を明確にする
// ステップ2: 遷移式を立てる
// dp[i] が dp[i-1] や dp[i-2] からどう計算されるか
// ステップ3: ベースケースを設定する
// dp[0], dp[1] など初期値を決める
// ステップ4: 計算順序を決める
// ボトムアップなら小さい方から、トップダウンなら再帰
// ステップ5: 答えを返す
// dp[n] が答えか、max(dp) が答えかを確認
2. グリーディが正しいか検証する
グリーディが正しいか不安なときは、小さい反例を探してみましょう。
// 反例が見つかった → DP を使う
// 反例が見つからない → グリーディの証明を試みる（交換法など）
3. グラフ問題の選択指針
// 最短経路が必要?
// 重みなし → BFS
// 重みあり（非負） → ダイクストラ
// 負の辺あり → Bellman-Ford
// 全頂点間 → Floyd-Warshall
// 順序関係が必要? → トポロジカルソート
// 連結成分が必要? → Union-Find or DFS
// サイクル検出? → DFS（バックエッジ）
4. 空間最適化を常に検討する
DP テーブル全体が不要で、直前の行（または数個の変数）だけで十分な場合は、空間計算量を削減できます。
// Before: O(n) 空間
dp = [0] * (n + 1)
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
// After: O(1) 空間
prev2, prev1 = 0, 1
for i in range(2, n + 1):
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
🔍 関連する問題
この記事に関連するクイズ問題:
- Q21: 動的計画法の基本（フィボナッチ、階段問題）
- Q22: ナップサック問題
- Q24: コイン問題（DP vs グリーディ）
- Q26: 編集距離
- Q31: グリッド上の経路数
- Q33: 最長増加部分列（LIS）
- Q35: BFS / DFS の使い分け
- Q36: 島の数（連結成分）
- Q38: トポロジカルソート
- Q39: ダイクストラ法（最短経路）
- Q40: バックトラッキング（N-Queens）
- Q48: 区間スケジューリング（グリーディ）
📝 まとめ
- DP の適用条件: 最適部分構造 + 部分問題の重なり。状態定義と遷移式が鍵
- DP パターン: フィボナッチ（線形DP）、ナップサック、コイン、編集距離、グリッド、LIS を押さえる
- 空間最適化: ローリング配列で O(n) や O(mn) を O(W) や O(n) に削減できる
- グリーディの条件: 貪欲選択性質が成り立つときのみ使える。反例が見つかれば DP に切り替える
- グラフ探索: BFS は最短経路（重みなし）、DFS は全探索に向く
- 最短経路: ダイクストラ（非負辺）、Bellman-Ford（負辺あり）、Floyd-Warshall（全頂点間）
- バックトラッキング: 枝刈りで探索空間を削減し、全探索を効率化する
次のステップ: まずフィボナッチとナップサックの DP を自力で書けるようにし、次にグラフ問題に挑戦しましょう！