05 · 动态规划（Dynamic Programming）

📅 预计 120 分钟　|　⭐ 本章主题：把大问题拆成可复用的小问题，存下来慢慢拼
📌 中英术语见文末

5.1 DP 适用条件 ⭐

动态规划 = "记住算过的东西，别再算第二遍"

先看一个生活场景：你从宿舍走到教学楼，要经过操场、图书馆、食堂几个必经点。你想知道走每条路线各花多少时间。动态规划的思路是：把"到操场最快"、"到图书馆最快"这些子问题答案都记在小本子上，走到食堂时直接查本子，而不是把前面的路重新走一遍。

动态规划（dynamic programming，DP）适用的问题必须同时满足两个条件：

  1. 最优子结构（optimal substructure）：全局最优解由子问题的最优解组合而成。大问题拆成小问题，小问题各自最优，拼起来就是大问题最优。
  2. 重叠子问题（overlapping subproblems）：递归展开时，同一个子问题被反复求解。只有重叠，才有"记下来复用"的价值。

对比区分：

  • 分治（第 02 章）：子问题互不重叠，比如归并排序左右两半没有交叉计算；
  • 动态规划：子问题大量重叠，比如斐波那契的 fib(3) 被算多次，所以值得记忆化。
# 一个天然带重叠子问题的例子：二项式系数 C(n, k) = C(n-1, k-1) + C(n-1, k)
# 朴素递归会反复算同一个 C(i, j)，正是 DP 的用武之地

💡 记忆口诀：DP 两条件——"子问题最优拼全局"（最优子结构）+"子问题反复被算"（重叠子问题）。没重叠，用不上 DP。

⚠️ 常见错误

  1. 只满足最优子结构就上 DP：如果子问题不重叠，记忆化毫无收益，分治或贪心可能更合适。
  2. 贪心错误时想不到 DP：贪心被反例击倒（如 {1,5,11} 零钱）时，DP 是保证正确性的常规替代。
  3. 把 DP 当"递归"：递归只是实现手段之一，DP 的灵魂是"状态定义 + 转移方程 + 复用"，不是递归本身。

5.2 状态与转移方程 ⭐

动态规划的全部秘密：状态 + 转移

所有 DP 问题都围绕两个概念展开：

  1. 状态（state）：一个"子问题的答案"存放在哪里、用什么表示。通常写成 dp[i]、dp[i][j] 这样的数组。状态定义是 DP 的灵魂——定义得对，转移自然水到渠成；定义得差，题目越做越乱。
  2. 转移方程（transition）：怎样从更小的状态推出更大的状态。它回答的问题是"dp[i] 是怎么由 dp[i-1]、dp[i-2] 等算出来的"。

解 DP 的标准三步套路：

  1. 定义状态：想清楚 dp[i]（或 dp[i][j]）代表什么；
  2. 写转移方程：找"上一个状态"到"当前状态"的关系；
  3. 定初始值与边界：最小的状态值是多少，从哪开始填。
# 三步套路的极简示例：dp[i] 表示"前 i 个数之和"
def prefix_sum(nums):
    n = len(nums)
    dp = [0] * (n + 1)                 # dp[0]=0 是初始值
    for i in range(1, n + 1):
        dp[i] = dp[i - 1] + nums[i - 1]   # 转移方程
    return dp

print(prefix_sum([1, 2, 3, 4]))
# 输出: [0, 1, 3, 6, 10]

填表的方向很重要：每个状态都只依赖"已经算出来"的更小状态，所以从初始值出发，按依赖顺序从小到大填，就是自底向上。

⚠️ 常见错误

  1. 状态定义含糊：dp[i] 是"前 i 个"还是"第 i 个"、含不含第 i 个，必须写清楚，否则转移必错。
  2. 转移方程漏条件：比如背包里"容量不够放不下"的分支忘了写，直接越界或错值。
  3. 初始值不完整：dp[0]、边界行/列不设好，后面的转移全部建立在错误基础上。

5.3 记忆化 vs 自底向上

同一种 DP，两种写法

DP 有两种实现风格，本质等价，写法不同：

① 记忆化递归（自顶向下，top-down）：从大问题出发递归分解，算过就存，用 lru_cache 或字典记录。

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

② 自底向上迭代（bottom-up）：从最小状态开始填表，一路推到目标状态。

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
对比 记忆化（自顶向下） 迭代（自底向上）
思路 递归 + 缓存 循环填表
优点 直观、只算用到的状态 无递归栈风险、常可省空间
缺点 可能栈溢出、有缓存开销 有时要先想清填表顺序
选择 思路清晰时先用 追求性能和稳定性时用

记忆化递归对"依赖关系复杂"的状态（如二维、难确定填表顺序）更好写；自底向上对"依赖方向明确、可以滚动数组"的问题更容易优化空间。两者答案一致，选顺手的。

💡 记忆口诀：自顶向下是"从大往小拆，边拆边记"；自底向上是"从小往大填，一步到位"。写不出来就换另一种写法。

⚠️ 常见错误

  1. 记忆化忘了缓存：只加了递归没加缓存，就是裸递归，照样指数爆炸。
  2. 自底向上填表顺序错：某个状态依赖还没算出的状态，得到错误结果；先画依赖图再定顺序。
  3. 两种写法混用：一会儿记忆化一会儿填表，同一个问题逻辑对不上，难排查。

5.4 斐波那契：DP 视角

从"递归爆炸"到"填表秒算"

第 02 章我们已经优化过斐波那契，这里从 DP 的视角重新组织一遍，作为"最简 DP"模板：

  1. 状态：dp[i] = 第 i 个斐波那契数；
  2. 转移：dp[i] = dp[i-1] + dp[i-2]；
  3. 初始：dp[0] = 0, dp[1] = 1。
def fib_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]      # 转移方程
    return dp[n]

print(fib_dp(10))
# 输出: 55

空间优化（滚动数组）：观察转移方程只用到 dp[i-1] 和 dp[i-2]，前面算过的全都不再需要——所以只用两个变量滚动即可，空间从 O(n) 降到 O(1)：

def fib_roll(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_roll(10))
# 输出: 55

这个"滚动"技巧在 0-1 背包等更复杂的问题里同样重要。

⚠️ 常见错误

  1. 能滚动却没滚动：状态只依赖前两个时，dp 数组是浪费，面试常追问空间优化。
  2. 滚动顺序写反：a, b = b, a + b 必须同步更新；写成 a = b; b = a + b 就错了（第二步的 a 已是 b）。
  3. 忽略 n <= 1 的边界：dp[1] = 1 在 n=0 时会越界。

5.5 爬楼梯 ⭐

一次爬 1 或 2 阶，爬 n 阶有几种方法？

问题：楼梯有 n 阶，每次可以爬 1 阶或 2 阶，问爬到顶共有多少种不同走法。

状态：dp[i] = 爬到第 i 阶的方法数。
转移：到达第 i 阶，只可能来自"从第 i-1 阶跨 1 步"或"从第 i-2 阶跨 2 步"，所以 dp[i] = dp[i-1] + dp[i-2]。
初始：dp[0] = 1（站在地面，1 种"什么都不走"的方式）、dp[1] = 1（跨 1 步）。

你会发现它和斐波那契同一个转移方程，只是初始值不同。

def climb_stairs(n):
    if n <= 1:
        return 1
    a, b = 1, 1                # a=dp[0], b=dp[1]
    for _ in range(2, n + 1):
        a, b = b, a + b        # 滚动到 dp[i]
    return b

print(climb_stairs(5))
# 输出: 8
# 走法：11111, 2111, 1211, 1121, 1112, 221, 212, 122

变体一：最多爬 3 阶 → dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
变体二：每阶有体力代价，求"最小体力" → 从求和改成取 min：dp[i] = min(dp[i-1], dp[i-2]) + cost[i]。这是"计数类 DP"与"最值类 DP"的两种典型形态。

# 最小体力爬楼梯：每阶有体力消耗，可以从第 0 或第 1 阶起跳
def min_cost_climb(cost):
    n = len(cost)
    a, b = cost[0], cost[1]      # 到第 0、1 阶的最小消耗
    for i in range(2, n):
        a, b = b, min(a, b) + cost[i]
    return min(a, b)             # 最后可停在 n-1 或 n-2 阶

print(min_cost_climb([10, 15, 20]))
# 输出: 15  → 从第 1 阶起跳，直接到顶，花 15

⚠️ 常见错误

  1. 初始值搞错：dp[0] 是 1 不是 0（空楼梯有 1 种走法），这直接影响结果。
  2. 把"计数"写成"最值"：问"多少种方法"是求和，问"最小体力"是取 min，别混。
  3. 变体里漏加当前代价：最值类转移通常要 + cost[i]，漏加答案偏小。

5.6 0-1 背包 ⭐

背包容量有限，怎么装价值最高？

问题：有 n 件物品，每件有重量 w[i] 和价值 v[i]，背包容量为 C。每件物品要么拿要么不拿（0-1），求能装下的最大总价值。

状态：dp[i][c] = 只考虑前 i 件物品、背包容量为 c 时能装的最大价值。
转移：对第 i 件物品，两种决策取最大：

  • 不拿：价值等于"前 i-1 件、容量 c" → dp[i-1][c]；
  • 拿：先腾出 w 的空间装它 → dp[i-1][c-w] + v（前提 c >= w）。

所以 dp[i][c] = max(dp[i-1][c], dp[i-1][c-w] + v)（c < w 时只有不拿一项）。

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(1, capacity + 1):
            if w > c:
                dp[i][c] = dp[i - 1][c]           # 放不下，只能不拿
            else:
                dp[i][c] = max(dp[i - 1][c],          # 不拿
                               dp[i - 1][c - w] + v)  # 拿
    return dp[n][capacity]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack(weights, values, 5))
# 输出: 7  → 拿物品 1 和 2：重量 2+3=5，价值 3+4=7

复杂度：状态数 O(n·C)，每次转移 O(1)，总 O(n·C)，空间 O(n·C)。

空间优化（一维滚动数组）：dp[i][c] 只依赖 dp[i-1][...]，可以只保留一行。但必须从大到小遍历容量——因为小容量行 dp[c-w] 若先被本轮更新，就再也拿不到"上一轮"的值了。

def knapsack_1d(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):   # 容量从大到小！
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

print(knapsack_1d([2, 3, 4, 5], [3, 4, 5, 6], 5))
# 输出: 7

为什么必须倒序：正序遍历时 dp[c-w] 可能已经被当前物品更新过，等于同一件物品拿了多次——那就变成"完全背包"了。倒序遍历正是 0-1 背包与完全背包的唯一代码差异（完全背包用正序）。

💡 记忆口诀：0-1 背包一维化，容量必须倒着扫；正着扫会重复拿，那是完全背包。

⚠️ 常见错误

  1. 一维优化后忘了倒序：正序遍历会把同一物品拿多次，得到的是完全背包的答案。
  2. 越界访问 dp[c-w]：c < w 时直接访问下标为负，必须先判断。
  3. 状态维度想错：dp[i] 表示"容量为 i 时最大价值"却丢了"物品维度"——一维化后必须按物品逐个更新，否则物品混合。

5.7 最长公共子序列 LCS ⭐

两个字符串，最长公共子序列多长？

问题：给定两个字符串 a 和 b，求它们最长公共子序列（longest common subsequence, LCS）的长度。子序列不要求连续，但要保持原顺序。比如 a="ABCBDAB"、b="BDCABA"，LCS 是 "BCBA" 或 "BDAB"，长度 4。

状态：dp[i][j] = a 的前 i 个字符与 b 的前 j 个字符的 LCS 长度。
转移，分两种情况：

  • a[i-1] == b[j-1]（最后一个字符相同）→ dp[i][j] = dp[i-1][j-1] + 1，两个字符都加入；
  • 不相等 → dp[i][j] = max(dp[i-1][j], dp[i][j-1])，至少丢掉一个末尾字符，取较大者。
def lcs_length(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 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[m][n]

print(lcs_length("ABCBDAB", "BDCABA"))
# 输出: 4  （例如 "BCBA" 或 "BDAB"）

复杂度：状态数 O(m·n)，转移 O(1)，总 O(m·n)，空间 O(m·n)。

回溯输出具体子序列：从 dp[m][n] 倒推——若两字符相等就记下并沿对角线回退，否则沿 dp[i-1][j] 与 dp[i][j-1] 中较大的一边走：

def lcs_trace(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 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])
    # 回溯
    res = []
    i, j = m, n
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            res.append(a[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(res))

print(lcs_trace("ABCBDAB", "BDCABA"))
# 输出: BCBA   （BDAB 也是合法的 LCS）

LCS 是二维 DP 的代表题，掌握它等于掌握了一大类"两个序列对齐"问题（如编辑距离）。

⚠️ 常见错误

  1. 误以为 LCS 必须连续：连续的是"最长公共子串"，LCS 允许跳着取，转移方程完全不同。
  2. 回退方向选错：回溯时选了较小的一边走，得到的不是最长公共子序列。
  3. 二维数组下标偏移忘 -1：a[i-1] 对应"前 i 个字符"，i 从 1 开始数，直接写 a[i] 会错位。

🧠 记忆口诀

  • DP 两条件：最优子结构 + 重叠子问题——子问题最优拼全局，反复出现才记忆。
  • 三步走：定义状态 → 写转移方程 → 定初始边界。
  • 两种写法：自顶向下边拆边记（记忆化），自底向上从小填到大（迭代）。
  • 斐波那契/爬楼梯：dp[i] = dp[i-1] + dp[i-2]，可滚动到 O(1)。
  • 0-1 背包：dp[i][c] = max(不拿, 拿)；一维化容量倒序遍历，正序变完全背包。
  • LCS：字符相等沿对角线加 1，不等取上下较大者；回溯反着走。

📌 中英术语表（本讲）

中文 English 说明
动态规划 dynamic programming 用子问题最优解递推全局最优
状态 state 子问题答案的存放表示
转移方程 transition 小状态推出大状态的公式
最优子结构 optimal substructure 全局最优含子问题最优
重叠子问题 overlapping subproblems 同一子问题被反复求解
记忆化 memoization 自顶向下 + 缓存
自底向上 bottom-up 从小状态迭代填表
自顶向下 top-down 从大问题递归分解
滚动数组 rolling array 只用若干变量压缩空间
爬楼梯问题 climbing stairs 计数型 DP 入门题
0-1 背包 0-1 knapsack 每件物品取或不取
完全背包 unbounded knapsack 每件物品可取无限次
最长公共子序列 LCS 保持顺序但不要求连续
最长公共子串 longest common substring 要求连续，与 LCS 不同
编辑距离 edit distance 两个字符串对齐类问题

⭐ 本章考点清单

  1. DP 适用条件：最优子结构 + 重叠子问题
  2. 状态定义与转移方程、三步套路（状态→转移→边界）
  3. 记忆化 vs 自底向上两种实现，优缺点与选择
  4. 斐波那契 DP 化：状态、转移、滚动数组到 O(1)
  5. 爬楼梯：dp[i]=dp[i-1]+dp[i-2]，初始值 dp[0]=1
  6. 计数型（求和）与最值型（取 min/max）转移的区别
  7. 0-1 背包：二维转移、O(n·C)、一维滚动数组倒序遍历
  8. 0-1 背包与完全背包的唯一区别（正序/倒序）
  9. LCS 长度与回溯输出；LCS 与最长公共子串的区别
  10. 边界处理：容量不足、n<=1、二维下标偏移 -1