目次を表示する

CS基礎：計算量とデータ構造

動的計画法 ── 「同じ計算を二度しない」

動的計画法 ── 「同じ計算を二度しない」

扱う概念：重複部分問題、最適部分構造、メモ化（Top-Down）、テーブル法（Bottom-Up）、状態遷移式、空間最適化

動的計画法 — 状態定義・遷移式・空間最適化

この章で何ができるようになるか：DP 問題を見たとき「状態」と「遷移」を定義し、メモ化またはテーブル法で実装できるようになる。

DP が効くための2つの条件

1. 重複部分問題（Overlapping Subproblems）
   → 同じ部分問題を何度も解く
   → 例: fib(5) = fib(4) + fib(3)、fib(4) = fib(3) + fib(2)
         fib(3) が2回計算される

2. 最適部分構造（Optimal Substructure）
   → 全体の最適解が、部分問題の最適解から構築できる
   → 例: 最短経路の一部は、やはり最短経路

フィボナッチ数列で理解する3つのアプローチ

再帰（素朴）— O(2^n)

def fib_naive(n: int) -> int:
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# fib(40) で既に数秒かかる
# 呼び出しツリーが指数的に爆発

メモ化（Top-Down）— O(n)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

# O(n) 時間、O(n) 空間

テーブル法（Bottom-Up）— O(n)

def fib_table(n: int) -> int:
    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]

# O(n) 時間、O(n) 空間

空間最適化 — O(1)

def fib_optimized(n: int) -> int:
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# O(n) 時間、O(1) 空間
# dp[i] が dp[i-1] と dp[i-2] にしか依存しないため

DP 問題の解き方フレームワーク

Step 1: 状態を定義する
  dp[i] = 「i 番目の要素まで考えたときの最適解」

Step 2: 遷移式を書く
  dp[i] = f(dp[j], ...)   (j < i)

Step 3: 初期条件を設定する
  dp[0] = ...

Step 4: 計算順序を決める
  Bottom-Up: 小さい方から大きい方へ

Step 5: 答えを返す
  dp[n] または max(dp)

典型パターン1：ナップサック問題

「重さ制限 W のバッグに、価値が最大になるようにアイテムを詰める」

def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int:
    """
    0-1 ナップサック: 各アイテムは1つだけ使える
    状態: dp[i][w] = i番目のアイテムまで見て、残り容量wのときの最大価値
    遷移: dp[i][w] = max(dp[i-1][w],                    # i番目を入れない
                         dp[i-1][w-weights[i]] + values[i])  # i番目を入れる
    """
    n = len(weights)
    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]  # 入れない場合
            if w >= weights[i-1]:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - weights[i-1]] + values[i-1])

    return dp[n][capacity]

# 空間最適化: dp[i] は dp[i-1] にしか依存しない → 1次元に圧縮
def knapsack_01_optimized(weights, values, capacity):
    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]

典型パターン2：最長増加部分列（LIS）

def lis_dp(nums: list[int]) -> int:
    """
    O(n²) 解法
    状態: dp[i] = nums[i] で終わる LIS の長さ
    遷移: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
    """
    n = len(nums)
    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)

def lis_binary_search(nums: list[int]) -> int:
    """
    O(n log n) 解法: 二分探索で「末尾が最小の LIS」を維持
    """
    from bisect import bisect_left
    tails = []  # tails[i] = 長さ i+1 の LIS の末尾の最小値
    for num in nums:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

# [10, 9, 2, 5, 3, 7, 101, 18]
# LIS = [2, 3, 7, 18] → 長さ 4

典型パターン3：コイン問題（完全ナップサック）

def coin_change(coins: list[int], amount: int) -> int:
    """
    最小枚数で amount を作る
    状態: dp[a] = 金額 a を作るための最小コイン数
    遷移: dp[a] = min(dp[a - coin] + 1) for coin in coins
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if a >= coin and dp[a - coin] != float('inf'):
                dp[a] = min(dp[a], dp[a - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

典型パターン4：編集距離（Edit Distance）

def edit_distance(word1: str, word2: str) -> int:
    """
    word1 を word2 に変換する最小操作数（挿入/削除/置換）
    状態: dp[i][j] = word1[:i] を word2[:j] に変換する最小操作数
    """
    m, n = len(word1), len(word2)
    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]

Top-Down vs Bottom-Up の選択

Top-Down（メモ化）Bottom-Up（テーブル）
実装再帰 + キャッシュループ + 配列
思考の方向自然（問題を分解）逆（小さい問題から積み上げ）
不要な部分問題計算しない（遅延）全て計算する
スタックオーバーフローあり得る（再帰深度）なし
空間最適化難しいしやすい
定数倍やや遅い（再帰オーバーヘッド）速い

まとめ

パターン状態遷移計算量
フィボナッチ型dp[i]dp[i-1] + dp[i-2]O(n)
ナップサックdp[i][w]入れる/入れないO(n × W)
LISdp[i]max(dp[j]+1)O(n²) / O(n log n)
コイン問題dp[amount]min(dp[a-coin]+1)O(n × amount)
編集距離dp[i][j]挿入/削除/置換の minO(m × n)
最長共通部分列dp[i][j]一致/不一致O(m × n)

DP のコツは「まず状態と遷移を日本語で書く」こと。コードは後。