Software Systems Atlas

中文

English

中文

English

主题

第 2 卷 / 第 13 章 / 第 2 课

13.2 经典动态规划问题 ​

前置：动态规划入门。本页用 0-1 背包练习容量维度，用 LCS 与编辑距离练习双序列前缀；代码明确输入合同，并用一维优化展示遍历方向的含义。

从最后一个选择反推依赖 ​

第一张问有限容量里怎样选择物资，第二张比较两份日志保留了多长的共同顺序，第三张计算把一份记录改成另一份至少需要多少次操作。它们看起来不同，建模步骤却相同：先给 dp 下标写一句完整定义，再从最后一个选择反推依赖。

一份可执行的参考实现 ​

背包的重量和价值必须是等长序列，重量为正整数、价值为整数，允许不选物品，因此负价值不会迫使答案为负。容量和金额为非负整数；硬币输入可迭代，每个币值为正整数，重复币值不影响答案但会重复计算。LCS 与编辑距离只接收字符串。函数不修改输入；数值合同不满足时抛 ValueError，字符串类型不符时抛 TypeError。

python
def knapsack_01(weights, values, capacity):
    if len(weights) != len(values):
        raise ValueError("weights and values must have equal length")
    if not isinstance(capacity, int) or capacity < 0:
        raise ValueError("capacity must be a non-negative integer")
    if any(not isinstance(weight, int) or weight <= 0 for weight in weights):
        raise ValueError("weights must be positive integers")
    if any(not isinstance(value, int) for value in values):
        raise ValueError("values must be integers")

    best = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for remaining in range(capacity, weight - 1, -1):
            best[remaining] = max(
                best[remaining],
                best[remaining - weight] + value,
            )
    return best[capacity]

def lcs_length(first, second):
    if not isinstance(first, str) or not isinstance(second, str):
        raise TypeError("first and second must be strings")
    previous = [0] * (len(second) + 1)
    for first_char in first:
        current = [0]
        for column, second_char in enumerate(second, start=1):
            if first_char == second_char:
                current.append(previous[column - 1] + 1)
            else:
                current.append(max(previous[column], current[column - 1]))
        previous = current
    return previous[-1]

def edit_distance(source, target):
    if not isinstance(source, str) or not isinstance(target, str):
        raise TypeError("source and target must be strings")
    previous = list(range(len(target) + 1))
    for row, source_char in enumerate(source, start=1):
        current = [row]
        for column, target_char in enumerate(target, start=1):
            if source_char == target_char:
                current.append(previous[column - 1])
            else:
                current.append(1 + min(
                    previous[column],      # 删除 source_char
                    current[column - 1],   # 插入 target_char
                    previous[column - 1],  # 替换
                ))
        previous = current
    return previous[-1]

def min_coin_count(coins, amount):
    if not isinstance(amount, int) or amount < 0:
        raise ValueError("amount must be a non-negative integer")
    coins = list(coins)
    if any(not isinstance(coin, int) or coin <= 0 for coin in coins):
        raise ValueError("coins must be positive integers")

    unreachable = amount + 1
    best = [unreachable] * (amount + 1)
    best[0] = 0
    for current in range(1, amount + 1):
        for coin in coins:
            if coin <= current:
                best[current] = min(best[current], best[current - coin] + 1)
    return -1 if best[amount] == unreachable else best[amount]

if __name__ == "__main__":
    assert knapsack_01([2, 3, 4, 5], [3, 4, 5, 6], 8) == 10
    assert knapsack_01([], [], 8) == 0
    assert lcs_length("abcde", "ace") == 3
    assert lcs_length("", "ace") == 0
    assert edit_distance("horse", "ros") == 3
    assert edit_distance("", "abc") == 3
    assert min_coin_count([1, 2, 5], 11) == 3
    assert min_coin_count([2], 3) == -1
    print("经典 DP 检查通过")

0-1 背包：反向遍历保存上一轮 ​

二维定义是：

text
dp[i][c] = 只看前 i 个物品、容量不超过 c 时的最大价值

第 i 个物品只有“不选”和“选一次”两种情况。压成一维后，best[c] 同时承载上一轮与当前轮。容量必须从大到小遍历，读取 best[c-weight] 时它才仍代表“尚未处理当前物品”的上一轮状态。

若改成从小到大，同一物品刚写入的小容量结果会被本轮再次读取，语义就变成可重复取用的完全背包。所谓“0-1 反向、完全正向”不是口诀本身，而是防止或允许当前物品在同一轮被重复使用。

示例最优值 10 来自重量 3 与 5 的两个物品，价值分别为 4 与 6。只返回数值无法告诉调用方具体选项；需要还原方案时，可保留二维表或保存不会被后续更新改写的历史选择。只给一维数组附一个可变的“前驱容量”，可能在回溯时误读后来的状态。

n 个物品、正容量 W 的常见时间上界是 O(nW)，空间 O(W)。若把 n=0 或 W=0 也写进同一个式子，初始化与输入检查计入后为 O(nW+n+W+1) 时间、O(W+1) 空间。这里把整数运算视为常数成本，W 是容量数值而不是输入位数。因此这属于伪多项式算法：容量若用二进制表示且数值巨大，O(W) 不能简单称作“输入规模的多项式”。

LCS：子序列不要求连续 ​

dp[i][j] 表示两个长度分别为 i、j 的前缀的最长公共子序列长度。末尾字符相等时，可以在两个更短前缀的答案后接上该字符；不等时，至少有一个末尾字符不属于某个最优答案，于是取“去掉 first 末尾”与“去掉 second 末尾”的较大值。

本页只返回长度，用两行把空间从 O(mn) 压到 O(n)。若要还原实际子序列，需要保留足够的选择信息，或采用能重算路径的算法。非空字符串时，时间为 Θ(mn)，m、n 分别是第一、第二个字符串的长度。包括空输入的统一写法是 Θ((m+1)(n+1)) 时间、Θ(n+1) 空间。若先把较短字符串放在第二位，可以把行宽降到两者长度的较小值。

LCS 与最长公共子串不同：子串必须连续，状态在字符不等时通常归零；子序列只要求相对次序不变。

编辑距离：三种操作对应三个邻格 ​

dp[i][j] 表示 source 前 i 个字符变成 target 前 j 个字符的最少操作数。字符不等时：

  • 删除 source 末尾：dp[i-1][j]；
  • 插入 target 末尾：dp[i][j-1]；
  • 替换末尾：dp[i-1][j-1]。

三种操作各加 1。空前缀到长度 j 的前缀需要 j 次插入，这就是首行；长度 i 的前缀到空串需要 i 次删除，这就是首列。非空字符串时为 Θ(mn) 时间、Θ(n) 两行空间；包括空输入时为 Θ((m+1)(n+1)) 时间、Θ(n+1) 空间，m、n 分别为 source、target 长度。

本页按 Python 字符串的 Unicode 码点序列比较，但没有做规范化。例如 edit_distance("é", "e\u0301") 为 2；若先做 NFC 规范化，结果为 0。Python 的 Unicode 规范化接口可统一规范等价形式，但不会把所有视觉相似字符变成相等，也不会自动按用户感知字符（字素簇）切分。相邻字符交换在本页也不是一个独立操作。

零钱兑换：状态图可能不可达 ​

best[a] 表示凑出金额 a 的最少硬币数。每个正币值可重复使用，转移读取较小金额。用 amount+1 作为不可达哨兵，是因为每枚硬币的整数币值至少为 1，凑出 amount 的方案便至多使用 amount 枚硬币；无需真的存在面值 1。

若币值包含 0 或负数，依赖关系不再严格指向更小金额，本页直接拒绝。金额 0 返回 0；没有硬币且金额大于 0 时返回 -1。设 k 为币值个数、A 为金额，包括复制币值和初始化，时间为 O(k+A(k+1)+1)，空间为 O(k+A+1)。这个按金额建表的算法也属于伪多项式。

动手检查状态含义 ​

  1. 把背包容量循环改成正向，用一个物品证明它会被重复使用。
  2. 为背包保留选择路径，并规定多组最优方案时的决胜规则。
  3. 手算 LCS("abc", "bac") 的表格，观察最优序列可能不唯一。
  4. 给编辑距离添加不同的插入、删除、替换代价，哪些边界要同步改变？
  5. 用 BFS 把小金额零钱兑换看成最短路，与 DP 结果随机对照。

离开状态表 ​

容量 DP 的循环方向决定当前物品能否重复使用；双序列 DP 的三个邻格对应删、插、替或跳过末尾。状态定义写得足够精确，边界和遍历顺序才有可验证的来源。

下一章转向 贪心算法：有些问题不必保留所有候选，只做一个可证明安全的局部选择。

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang