動的計画法 - データサイエンス関連+αのメモ

概要¶

動的計画法（Dynamic Programming, DP） は、問題を小さな部分問題に分割し、その結果を記録・再利用することで効率的に解くアルゴリズム設計手法である。

適用条件¶

性質	説明
最適部分構造	問題の最適解が部分問題の最適解から構成できる
重複する部分問題	同じ部分問題が複数回現れる（単純な再帰では無駄な計算が発生する）

貪欲法との違い¶

	貪欲法	動的計画法
選択方法	局所最適を逐次選択	全部分問題の最適解を記録して利用
後戻り	しない	しない（ただし全パターンを網羅）
適用範囲	貪欲選択性が成立する問題	最適部分構造 + 重複部分問題がある問題
計算量	一般に速い	貪欲法より遅いが再帰より大幅に速い

2つのアプローチ¶

トップダウン（メモ化再帰）: 再帰で解きながら、計算済みの結果をキャッシュする
ボトムアップ（表形式）: 小さい部分問題から順に解いてテーブルに埋める

参考文献

競技プログラミングにおける動的計画法問題まとめ - はまやんはまやんはまやん

例1: フィボナッチ数列¶

$F(n) = F(n-1) + F(n-2)$ は重複する部分問題の典型例。単純な再帰では $O(2^n)$ かかるが、DP では $O(n)$ になる。

%%timeit
import functools

# トップダウン（メモ化再帰）
@functools.cache
def fib_top_down(n: int) -> int:
    if n <= 1:
        return n
    # 素直に再帰関数にするので O(2^n)
    return fib_top_down(n - 1) + fib_top_down(n - 2)

n = 1000
fib_top_down(n)

102 μs ± 730 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

%%timeit
# ボトムアップ（表形式）
def fib_bottom_up(n: int) -> int:
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    
    # 状態を配列に保存してforループにする → O(n)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

fib_bottom_up(n)

200 ns ± 2.37 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

例2: 0/1 ナップサック問題¶

Q. 容量 $W$ のナップサックに重さ $w_i$ ・価値 $v_i$ のアイテムを詰めるとき、価値を最大化するには？ アイテムは分割できない（0/1: 使うか使わないか）。

分数ナップサックと異なり、貪欲法では最適解が保証されないため DP を使う。

漸化式

dp[i][j] = \max(dp[i-1][j],\; dp[i-1][j - w_i] + v_i) \quad (j \geq w_i)

(1)

$dp[i][j]$ : 最初の $i$ 個のアイテムから容量 $j$ で得られる最大価値

def knapsack_01(capacity: int, items: list[tuple[int, int]]) -> int:
    """
    0/1 ナップサック問題

    Parameters
    ----------
    capacity : int
    items : list of (weight, value)

    Returns
    -------
    int
        最大価値
    """
    n = len(items)
    # dp[j]: 容量 j での最大価値（1次元配列で空間節約）
    dp = [0] * (capacity + 1)

    for weight, value in items:
        for j in range(capacity, weight - 1, -1):  # 逆順で更新（同アイテムの重複使用を防ぐ）
            dp[j] = max(dp[j], dp[j - weight] + value)

    return dp[capacity]


capacity = 50
items = [
    (10, 60),
    (20, 100),
    (30, 120),
]

print(f"最大価値: {knapsack_01(capacity, items)}")
# 分数ナップサックは 240 だが 0/1 では最適解が異なることを確認
# アイテム(10,60)+(20,100)+(20/30*30, 80) = 240 → 分割できないので
# 選択肢: (10,60)+(20,100) = 160 or (20,100)+(30,120) = 220 or (10,60)+(30,120) = 180
print("  ※ 分数ナップサックの場合は 240 になる")

最大価値: 220
  ※ 分数ナップサックの場合は 240 になる

例3: 最長共通部分列（LCS）¶

Q. 2つの文字列 $s$ 、 $t$ の最長共通部分列（Longest Common Subsequence）の長さは？

部分列は連続でなくてもよい（例: "ACE" は "ABCDE" の部分列）。

漸化式

dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & (s[i] = t[j]) \\ \max(dp[i-1][j],\; dp[i][j-1]) & (s[i] \neq t[j]) \end{cases}

(2)

def lcs_dp(s: str, t: str) -> list[list[int]]:
    """2つの文字列 s, t の LCS（Longest Common Subsequence: 最長共通部分列）の長さのDPテーブル"""
    m, n = len(s), len(t)

    # dp[i][j]: s の先頭 i 文字と、t の先頭 j 文字を見たときの LCS の長さ
    # +1 しているのは、空文字 "" との比較も扱うため
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # s の先頭から i 文字目までを見る
    # i は 1 から始める。なぜなら dp[0][*] は「s が空文字」の場合として使うため
    for i in range(1, m + 1):
        # t の先頭から j 文字目までを見る
        for j in range(1, n + 1):
            # Python の添字は 0 始まりなので、i 文字目を見るには i - 1 を使う
            if s[i - 1] == t[j - 1]:
                # sのi文字目とtのj文字目が一致した場合、その文字を LCS に追加できる
                # したがって、
                # 「1つ前の状態 dp[i - 1][j - 1]」に 1 を足す
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # 文字が一致しない場合、
                # s の i 文字目を使わないか、
                # t の j 文字目を使わないかを選ぶ
                #
                # dp[i - 1][j]: s の i 文字目を使わない場合（1文字減らす）
                # dp[i][j - 1]: t の j 文字目を使わない場合
                # より長い LCS になる方を採用する
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp


def lcs_length(s: str, t: str) -> int:
    """2つの文字列 s, t の LCS（Longest Common Subsequence: 最長共通部分列）の長さを求める関数。"""
    dp = lcs_dp(s, t)
    # dp[m][n] は、s 全体と t 全体を見たときの LCS の長さ
    m, n = len(s), len(t)
    return dp[m][n]


s, t = "ABCBDAB", "BDCAB"
print(f"s = {s!r}")
print(f"t = {t!r}")
print(f"LCS の長さ: {lcs_length(s, t)}")

s = 'ABCBDAB'
t = 'BDCAB'
LCS の長さ: 4

def lcs_string(s: str, t: str) -> str:
    """2つの文字列 s, t の LCS の具体例を1つ復元する関数。"""
    m, n = len(s), len(t)
    dp = lcs_dp(s, t)


    # -------------------------
    # ここから経路復元
    # -------------------------

    # result に LCS の文字を後ろから追加していく
    result = []

    # dp[m][n] から逆向きにたどる
    # つまり、s 全体・t 全体を見た状態からスタートする
    i, j = m, n

    # i または j が 0 になるまで戻る
    # i == 0 は s が空文字になった状態
    # j == 0 は t が空文字になった状態
    while i > 0 and j > 0:

        # s の i 文字目と t の j 文字目が一致している場合
        if s[i - 1] == t[j - 1]:

            # この文字は LCS に含まれる
            #
            # ただし、後ろから復元しているので、
            # result には逆順で入っていく
            result.append(s[i - 1])

            # 一致した文字を使ったので、
            # 左上のマスに戻る
            i -= 1
            j -= 1

        # 上のマス dp[i - 1][j] の方が大きい場合
        elif dp[i - 1][j] > dp[i][j - 1]:

            # s の i 文字目は LCS に使わないと判断し、
            # i を 1 つ戻す
            i -= 1

        else:
            # 左のマス dp[i][j - 1] の方が大きい、
            # または同じ大きさの場合
            #
            # t の j 文字目は LCS に使わないと判断し、
            # j を 1 つ戻す
            #
            # 同じ大きさの場合は、どちらに進んでも
            # LCS の長さは変わらない。
            # この実装では左に進む。
            j -= 1

    # result は後ろから追加されているため逆順になっている
    # そのため reversed(result) で正しい順番に戻す
    return "".join(reversed(result))


print(f"LCS の例 : {lcs_string(s, t)!r}")

LCS の例 : 'BDAB'

参考文献¶

動的計画法（ナップサック問題） - アルゴリズム講習会