リリース・改善中
動的計画法 ガイド · 2/6
この章は現在、英語でのみ提供しています。
Most DP solutions are designed with the same five questions. This chapter applies them to two classic problems, minimum coin change and longest common subsequence (LCS), and traces the tables by hand so you can see the answers being built.
Given coin denominations [1, 3, 4] (unlimited supply of each) and an amount of 6, what is the fewest number of coins that adds up to exactly 6?
A greedy approach takes the largest coin first: 4, then 1, then 1, which is three coins. But 3 + 3 uses only two. Greedy fails, so we use DP.
dp[a] = fewest coins that sum to amount a.dp[a] = 1 + min(dp[a - c]) over every coin c with c <= a.dp[0] = 0. Unreachable amounts stay at infinity.a, because dp[a] depends only on smaller amounts.dp[6].Filling the table from left to right:
| a | Candidates (coin: 1 + dp[a - coin]) | dp[a] | Last coin |
|---|---|---|---|
| 0 | base case | 0 | - |
| 1 | 1: 1 + 0 | 1 | 1 |
| 2 | 1: 1 + 1 | 2 | 1 |
| 3 | 1: 1 + 2, 3: 1 + 0 | 1 | 3 |
| 4 | 1: 1 + 1, 3: 1 + 1, 4: 1 + 0 | 1 | 4 |
| 5 | 1: 1 + 1, 3: 1 + 2, 4: 1 + 1 | 2 | 1 |
| 6 | 1: 1 + 2, 3: 1 + 1, 4: 1 + 2 | 2 | 3 |
The answer is dp[6] = 2. Following the "Last coin" column backwards gives the coins themselves: from 6 take a 3 and move to 3, take a 3 and move to 0.
import math
def min_coins(coins: list[int], amount: int) -> tuple[int, list[int]]:
dp = [0] + [math.inf] * amount
last = [0] * (amount + 1)
for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
last[a] = c
if dp[amount] == math.inf:
return -1, []
used, a = [], amount
while a > 0:
used.append(last[a])
a -= last[a]
return dp[amount], used
print(min_coins([1, 3, 4], 6)) # (2, [3, 3])
print(min_coins([5, 10], 3)) # (-1, [])The same recurrence written top-down reads almost like the definition. The cache makes sure each amount is solved only once.
import math
from functools import cache
def min_coins(coins: tuple[int, ...], amount: int) -> int:
@cache
def best(a: int) -> float:
if a == 0:
return 0
return min((1 + best(a - c) for c in coins if c <= a), default=math.inf)
result = best(amount)
return -1 if result == math.inf else int(result)
print(min_coins((1, 3, 4), 6)) # 2A subsequence keeps characters in order but may skip some. For a = "ABCBA" and b = "BCAB", what is the longest string that is a subsequence of both?
L[i][j] = LCS length of the first i characters of a and the first j characters of b.a[i-1] == b[j-1], then L[i][j] = L[i-1][j-1] + 1; otherwise L[i][j] = max(L[i-1][j], L[i][j-1]).L[0][j] = L[i][0] = 0 (an empty prefix shares nothing).L[5][4].| "" | B | C | A | B | |
|---|---|---|---|---|---|
| "" | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 2 |
| C | 0 | 1 | 2 | 2 | 2 |
| B | 0 | 1 | 2 | 2 | 3 |
| A | 0 | 1 | 2 | 3 | 3 |
The bottom-right cell says the LCS has length 3. To recover one, start there and walk back: on a match, take the character and move diagonally; otherwise move toward the larger neighbor. Ties can lead to different but equally long answers, such as "BCB" and "BCA".
def lcs_table(a: str, b: str) -> list[list[int]]:
L = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
L[i][j] = L[i - 1][j - 1] + 1
else:
L[i][j] = max(L[i - 1][j], L[i][j - 1])
return L
for row in lcs_table("ABCBA", "BCAB"):
print(row)
# last row printed: [0, 1, 2, 3, 3]
コメント 0件
ログイン · ログインするとコメントできます。
最初のコメントを書いてみましょう。