动态规划详解：原理、代码与示例

动态规划解决什么问题

许多问题要求最好、最便宜或方案数：凑出某个金额所需的最少硬币数、两个字符串的最长公共子序列、背包能装下的价值最高的物品组合、穿过网格的路径条数。直接的递归解法往往会把相同的小问题重复计算指数次，DP 消除了这种重复。

这个名字来自 Richard Bellman，他在 20 世纪 50 年代发展了这一方法。这里的“programming”指的是规划或填表，而不是编写代码。

用大白话讲思路

朴素的递归斐波那契就暴露了问题。fib(5) 会调用 fib(4) 和 fib(3)，而 fib(4) 又会再次调用 fib(3)，依此类推：调用次数呈指数增长。如果每个结果在第一次算出时就存起来，之后的每次调用都是瞬间完成。

1. 定义状态：子问题长什么样？例如，best[a] = 凑出金额 a 所需的最少硬币数。
2. 写出递推式：如何由更小的状态算出当前状态？best[a] = 1 + min(best[a - c] for each coin c)。
3. 设定边界条件：best[0] = 0。
4. 选择计算顺序：自顶向下用记忆化，或自底向上，保证更小的状态总是先被填好。
5. 从对应的状态读出答案，需要时再还原出具体的选择。

自顶向下：用 functools 实现记忆化

在 Python 中，functools.cache（Python 3.9+）或 functools.lru_cache 只需一行就能给函数加上记忆化：

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(80))  # 23416728348467685

没有这个装饰器，fib(80) 会产生超过 10¹⁶ 次递归调用。加上之后，0 到 80 的每个值只计算一次。

实例：自底向上的零钱兑换

硬币面值为 1、3、4，金额为 6。贪心法先取 4，需要 4 + 1 + 1 共 3 枚硬币，但 3 + 3 只需 2 枚。DP 通过对 a = 0 到 6 依次填写 best[a]，找到真正的最小值：

def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

print(min_coins([1, 3, 4], 6))  # 2
print(min_coins([2], 3))        # -1

二维示例：最长公共子序列

许多针对两个序列的 DP 问题会用到网格：dp[i][j] 表示一个字符串的前 i 个字符与另一个字符串的前 j 个字符的答案。对最长公共子序列（LCS），如果两个字符相同，就沿对角线延伸；否则，取分别丢掉任一字符串的一个字符后更好的结果。

def lcs(a, b):
    dp = [[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]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[len(a)][len(b)]

print(lcs("ABCBDAB", "BDCABA"))  # 4

一个长度为 4 的 LCS 是 BCBA。同样的表格结构也能解决编辑距离问题，文本比较（diff）工具正是用它来衡量两个字符串的差异程度。

时间与空间复杂度

通用规则：时间 = 状态数 × 每个状态的计算量；空间 = 需要保存的状态数。

背包问题的 O(n × W) 是伪多项式的：它取决于数值 W，而不是输入的位数，所以 W 很大时会很慢。

常见错误与何时使用 DP

• 状态定义错误：如果递推需要状态中没有的信息（例如哪些物品已被使用），答案就会出错。请把这些信息加入状态。
• 填表顺序错误：自底向上的循环必须保证每个状态在被读取之前已经算好。
• 表格大小差一：长度为 n 的字符串需要 n + 1 行，才能包含空前缀。
• 递归过深：对 10,000 个状态做记忆化递归可能超出 Python 的递归深度限制；请改为自底向上。
• 参数不可哈希：functools.cache 要求参数可哈希，所以请传元组而不是列表。

典型的面试题和实际应用：爬楼梯、打家劫舍、最长递增子序列、单词拆分、网格中的不同路径、编辑距离、背包、矩阵链乘法；实际中还有生物信息学中的序列比对、diff 工具、拼写检查、语音识别（Viterbi 算法）以及 Bellman-Ford 等最短路径算法。