動的計画法#
概要#
動的計画法（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)
275 μs ± 1.26 μs per loop (mean ± std. dev. of 7 runs, 1,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)
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
Cell In[2], line 1
----> 1 get_ipython().run_cell_magic('timeit', '', '# ボトムアップ（表形式）\ndef fib_bottom_up(n: int) -> int:\n if n <= 1:\n return n\n dp = [0] * (n + 1)\n dp[1] = 1\n \n # 状態を配列に保存してforループにする → O(n)\n for i in range(2, n + 1):\n dp[i] = dp[i - 1] + dp[i - 2]\n return dp[n]\n\nfib_bottom_up(n)\n')
File ~/work/notes/notes/.venv/lib/python3.10/site-packages/IPython/core/interactiveshell.py:2543, in InteractiveShell.run_cell_magic(self, magic_name, line, cell)
2541 with self.builtin_trap:
2542 args = (magic_arg_s, cell)
-> 2543 result = fn(*args, **kwargs)
2545 # The code below prevents the output from being displayed
2546 # when using magics with decorator @output_can_be_silenced
2547 # when the last Python token in the expression is a ';'.
2548 if getattr(fn, magic.MAGIC_OUTPUT_CAN_BE_SILENCED, False):
File ~/work/notes/notes/.venv/lib/python3.10/site-packages/IPython/core/magics/execution.py:1209, in ExecutionMagics.timeit(self, line, cell, local_ns)
1207 for index in range(0, 10):
1208 number = 10 ** index
-> 1209 time_number = timer.timeit(number)
1210 if time_number >= 0.2:
1211 break
File ~/work/notes/notes/.venv/lib/python3.10/site-packages/IPython/core/magics/execution.py:174, in Timer.timeit(self, number)
172 gc.disable()
173 try:
--> 174 timing = self.inner(it, self.timer)
175 finally:
176 if gcold:
File <magic-timeit>:13, in inner(_it, _timer)
NameError: name 'n' is not defined
例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)
\]
\(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" の部分列）。
漸化式
\[\begin{split}
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}
\end{split}\]
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'