- Authors
- Name
- Youngju Kim
- @fjvbn20031
FAANG コーディング面接完全攻略: 動的計画法パターン
動的計画法（DP）は FAANG 面接で最も頻繁に出題されるトピックの一つです。このガイドでは、面接で必ず知っておくべき DP パターンを体系的に解説します。
1. DP アプローチの体系
DP 問題の見分け方
動的計画法の問題には二つの核心的な特性があります。
最適部分構造 (Optimal Substructure)
- 全体問題の最適解が部分問題の最適解から構成される
- 例: 最短経路 A→C は A→B の最短 + B→C の最短の合計
重複する部分問題 (Overlapping Subproblems)
- 同じ部分問題が複数回繰り返し現れる
- フィボナッチ数列: fib(5) = fib(4) + fib(3)、fib(4) = fib(3) + fib(2) → fib(3) が重複
DP 問題の認識シグナル
- 「最大」「最小」「最長」「最短」を求める問題
- 「何通りの方法があるか」といったカウント問題
- 「可能かどうか」という判定問題
- 配列や文字列で部分構造を探索する問題
トップダウン vs ボトムアップの比較
# トップダウン (メモ化) - 再帰 + キャッシュ
def fib_topdown(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_topdown(n-1, memo) + fib_topdown(n-2, memo)
return memo[n]
# ボトムアップ (表形式) - 繰り返し + テーブル
def fib_bottomup(n):
if n <= 1:
return 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]
| 特性 | トップダウン | ボトムアップ |
|---|---|---|
| アプローチ | 再帰 + メモ化 | 繰り返し + テーブル |
| 直感性 | 問題を自然に分解 | 順序を先に把握する必要あり |
| 空間 | コールスタックのオーバーヘッド | テーブル空間のみ |
| 速度 | 必要な部分のみ計算 | すべての状態を計算 |
| 最適化 | 難しい | 空間最適化が可能 |
DP 設計 4 ステップ
- 状態定義: dp[i] が何を意味するかを明確に定義
- 漸化式: dp[i] を以前の状態で表現
- 基底ケース: 初期値の設定
- 計算順序: 依存関係に基づく計算順序の決定
2. 1D DP パターン
Climbing Stairs (LeetCode 70)
def climbStairs(n: int) -> int:
if n <= 2:
return n
# dp[i] = i 段目に到達する方法の数
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# 空間最適化: O(n) -> O(1)
def climbStairs_optimized(n: int) -> int:
if n <= 2:
return n
prev, curr = 1, 2
for _ in range(3, n + 1):
prev, curr = curr, prev + curr
return curr
- 時間計算量: O(n)
- 空間計算量: O(1) (最適化バージョン)
House Robber (LeetCode 198)
def rob(nums: list) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
# dp[i] = 0 から i 番目の家まで盗める最大金額
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
# 空間最適化
def rob_optimized(nums: list) -> int:
prev2, prev1 = 0, 0
for num in nums:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1
House Robber II (LeetCode 213)
円形配列: 最初と最後の家を同時に選択できません。
def rob2(nums: list) -> int:
def rob_linear(houses):
prev2, prev1 = 0, 0
for h in houses:
prev2, prev1 = prev1, max(prev1, prev2 + h)
return prev1
if len(nums) == 1:
return nums[0]
# 最初の家を含む (最後を除く) vs 最後の家を含む (最初を除く)
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
Maximum Product Subarray (LeetCode 152)
負の数があるため、最小値も追跡する必要があります。
def maxProduct(nums: list) -> int:
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
# 負の数 * 負の最小値 = 正の最大値になる可能性
candidates = (num, max_prod * num, min_prod * num)
max_prod = max(candidates)
min_prod = min(candidates)
result = max(result, max_prod)
return result
- 時間計算量: O(n)
- 空間計算量: O(1)
Jump Game I および II (LeetCode 55, 45)
# Jump Game I: 最後のインデックスに到達できるか
def canJump(nums: list) -> bool:
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach:
return False
max_reach = max(max_reach, i + jump)
return True
# Jump Game II: 最少ジャンプ回数
def jump(nums: list) -> int:
jumps = current_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end:
jumps += 1
current_end = farthest
return jumps
Longest Increasing Subsequence (LeetCode 300)
# O(n^2) DP アプローチ
def lengthOfLIS(nums: list) -> int:
n = len(nums)
# dp[i] = nums[i] で終わる LIS の長さ
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# O(n log n) 二分探索アプローチ
import bisect
def lengthOfLIS_nlogn(nums: list) -> int:
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
3. 2D DP パターン
Unique Paths (LeetCode 62)
def uniquePaths(m: int, n: int) -> int:
# dp[i][j] = (0,0) から (i,j) までの経路数
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]
# 空間最適化: 1D 配列
def uniquePaths_optimized(m: int, n: int) -> int:
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1]
return dp[-1]
Minimum Path Sum (LeetCode 64)
def minPathSum(grid: list) -> int:
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
# 最初の行を初期化
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
# 最初の列を初期化
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[m-1][n-1]
Longest Common Subsequence (LeetCode 1143)
def longestCommonSubsequence(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
# dp[i][j] = text1[:i] と text2[:j] の LCS の長さ
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
- 時間計算量: O(m * n)
- 空間計算量: O(m * n)、最適化すると O(min(m, n))
Edit Distance (LeetCode 72)
def minDistance(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
# dp[i][j] = word1[:i] を word2[:j] に変換する最小操作数
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 基底ケース
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(
dp[i-1][j], # 削除
dp[i][j-1], # 挿入
dp[i-1][j-1] # 置換
)
return dp[m][n]
Coin Change (LeetCode 322)
def coinChange(coins: list, amount: int) -> int:
# dp[i] = 金額 i を作るのに必要な最小コイン数
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Coin Change 2 (LeetCode 518)
def change(amount: int, coins: list) -> int:
# dp[i] = 金額 i を作る方法の数 (非有界ナップサック問題)
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
0/1 ナップサック問題
def knapsack(weights: list, values: list, capacity: int) -> int:
n = len(weights)
# dp[i][w] = i 番目のアイテムまで考慮し重さ w 以下での最大価値
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
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][capacity]
# 空間最適化: 逆順走査
def knapsack_optimized(weights: list, values: list, capacity: int) -> int:
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
4. 区間 DP (Interval DP)
区間 DP は連続した部分配列や部分文字列 [i, j] に対して最適解を求めるパターンです。 重要な洞察: dp[i][j] = i から j の区間における最適値
Burst Balloons (LeetCode 312)
def maxCoins(nums: list) -> int:
# 両端に仮想の 1 を追加
nums = [1] + nums + [1]
n = len(nums)
# dp[i][j] = nums[i+1..j-1] の風船をすべて割って得られる最大コイン
dp = [[0] * n for _ in range(n)]
# 長さ 2 から開始 (隣接する境界の間に風船がない)
for length in range(2, n):
for left in range(n - length):
right = left + length
for k in range(left + 1, right):
# k を区間 [left, right] で最後に割る風船とする
coins = nums[left] * nums[k] * nums[right]
dp[left][right] = max(
dp[left][right],
dp[left][k] + coins + dp[k][right]
)
return dp[0][n-1]
- 時間計算量: O(n^3)
- 空間計算量: O(n^2)
Palindromic Substrings (LeetCode 647)
def countSubstrings(s: str) -> int:
n = len(s)
# dp[i][j] = s[i..j] が回文なら True
dp = [[False] * n for _ in range(n)]
count = 0
# 長さ 1: 常に回文
for i in range(n):
dp[i][i] = True
count += 1
# 長さ 2
for i in range(n - 1):
if s[i] == s[i+1]:
dp[i][i+1] = True
count += 1
# 長さ 3 以上
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
count += 1
return count
Longest Palindromic Subsequence (LeetCode 516)
def longestPalindromeSubseq(s: str) -> int:
n = len(s)
# dp[i][j] = s[i..j] における最長回文部分列の長さ
dp = [[0] * n for _ in range(n)]
# 長さ 1: 常に 1
for i in range(n):
dp[i][i] = 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
行列チェーン乗算の概念
行列 A1 _ A2 _ ... * An の積の演算回数を最小化する問題です。
- dp[i][j] = 行列 i から j を掛け合わせる最小演算数
- 漸化式:
dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j])withi <= k < j
5. 木とグラフの DP
House Robber III (LeetCode 337)
隣接するノードを同時に選択できない木での最大合計を求めます。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob3(root: TreeNode) -> int:
def dfs(node):
if not node:
return (0, 0) # (選択しない, 選択する)
left_no, left_yes = dfs(node.left)
right_no, right_yes = dfs(node.right)
# 現在のノードを選択しない: 子は選択してもしなくてもよい
not_rob = max(left_no, left_yes) + max(right_no, right_yes)
# 現在のノードを選択する: 子は選択不可
rob = node.val + left_no + right_no
return (not_rob, rob)
return max(dfs(root))
Unique Binary Search Trees (LeetCode 96)
def numTrees(n: int) -> int:
# dp[i] = i ノードで構成できる構造的に異なる BST の数 (カタラン数)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for nodes in range(2, n + 1):
for root in range(1, nodes + 1):
left_count = dp[root - 1]
right_count = dp[nodes - root]
dp[nodes] += left_count * right_count
return dp[n]
6. FAANG DP 出題傾向
Hard 難易度の DP 問題を好む傾向があります。
- Burst Balloons、Regular Expression Matching、Wildcard Matching
- 複雑な状態空間を持つ問題 (3D DP など)
- 区間 DP やビットマスク DP
準備のポイント: 再帰から始めてメモ化を追加し、最後にボトムアップに変換する練習をしましょう。
Meta (Facebook)
実用的な Medium 難易度の DP 問題が多いです。
- Coin Change、Longest Common Subsequence
- Decode Ways、Word Break
- 製品に関連する DP 問題
準備のポイント: コードの簡潔さと説明能力が重要です。漸化式を先に説明してからコードを書きましょう。
Amazon
実用的な Medium DP 問題が中心です。
- House Robber シリーズ、Jump Game
- Longest Increasing Subsequence、Maximum Subarray
- システム設計に連携した最適化問題
準備のポイント: アルゴリズムの説明をリーダーシップ原則と結びつけると良いです。
状態空間の最適化
多くの 2D DP を 1D に最適化できます。
# LCS: 2D から 1D への最適化
def lcs_optimized(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
if m < n:
text1, text2 = text2, text1
m, n = n, m
# 前の行のみを保持
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev = curr
return prev[n]
最適化の原則:
- 現在の行が前の行にのみ依存 → ローリング配列 (2D → 1D)
- 現在の値が直前の値にのみ依存 → 変数 2 つ (1D → O(1))
- 逆順走査で 0/1 ナップサックの空間を節約
7. 練習問題クイズ
クイズ 1: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) という漸化式を使う問題はどれですか？
答え: House Robber
解説: dp[i] は 0 から i 番目の家まで考慮したときに盗める最大金額を表します。i 番目の家を盗む場合は i-1 番目は選べないので dp[i-2] + nums[i]、盗まない場合は dp[i-1] となり、この 2 つの最大値を取ります。
クイズ 2: Coin Change 問題で dp[0] = 0 に初期化する理由は？
答え: 金額 0 を作るのに必要なコインの枚数が 0 だからです。
解説: dp[0] = 0 は基底ケースで、金額 0 はコインを使わなくても達成できます。dp[1]、dp[2] などはすべてこの基底ケースをもとに計算されます。dp[0] が 0 でない場合、すべての計算値が誤りになります。
クイズ 3: LCS で dp[i][j] = dp[i-1][j-1] + 1 が成立する条件は？
答え: text1[i-1] == text2[j-1] のとき、つまり現在比較している 2 文字が同じとき
解説: 2 文字が一致する場合、これまでの LCS に現在の文字を追加できるので dp[i-1][j-1] + 1 となります。一致しない場合は max(dp[i-1][j], dp[i][j-1]) を取ります。
クイズ 4: Burst Balloons で k を「最後に割る風船」と定義する理由は？
答え: 部分問題を独立に分離するためです。
解説: k を「最初に割る風船」と定義すると、割った後に隣接関係が変わり、2 つの部分問題が独立でなくなります。k を「最後の風船」と定義することで、[left, k] と [k, right] の区間がそれぞれ独立に計算でき、k が最後に割られるときのスコアは常に nums[left] _ nums[k] _ nums[right] に固定されます。
クイズ 5: O(n log n) の LIS アルゴリズムで tails 配列が表すものは？
答え: tails[i] は長さ i+1 の増加部分列で取り得る最小の末尾値です。
解説: tails 配列は実際の LIS を表さず、各長さの LIS が持てる最小の末尾値を格納します。これにより、新しい数がどこに挿入されるかを二分探索で O(log n) に見つけられます。tails 配列の最終的な長さが LIS の長さになります。
まとめ
動的計画法はパターンを習得すれば体系的に取り組めるようになります。
推奨学習順序:
- Climbing Stairs、Fibonacci (DP の基礎)
- House Robber シリーズ (1D DP)
- Unique Paths、Minimum Path Sum (2D DP)
- LCS、Edit Distance (文字列 DP)
- Coin Change (ナップサック問題)
- Burst Balloons (区間 DP)
- House Robber III (木の DP)
面接のポイント:
- 常に状態定義から始める
- 漸化式を言葉で説明してからコードを書く
- ブルートフォース → メモ化 → 表形式の順に最適化する
- 時間計算量と空間計算量を常に分析する