已發布·持續改進
動態規劃 指南 · 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 則留言
登入 · 登入後即可留言。
來留下第一則留言吧。