6.2 动态规划：以空间换时间的记忆内功

6.2 动态规划：以空间换时间的记忆内功

本节摘要：动态规划（DP）治一类特殊问题：子问题相互重叠、且大问题的最优解由小问题的最优解拼成。做法是定义状态、写出转移方程、按依赖顺序填表，每个子问题只算一次。本节从爬楼梯的台阶计数进入 0-1 背包，填出完整的状态表并做滚动数组优化，最后给出三个高频翻车点。承接 1.3 节的记忆化伏笔。

三条门槛，一条心法

不是所有问题都配用动态规划。它要求：

• 最优子结构：大问题的最优解包含小问题的最优解。最短路天然满足（最短路的一段也是最短路）；
• 重叠子问题：不同决策路径会反复落到同一个子问题上。斐波那契是最小样本（1.3 节已数过：两万余次调用，其实只有几十个不同子问题）；
• 无后效性：某状态一旦确定，之后的演变不再受"怎么到达它"的影响。今天剩多少钱、走到哪格是全部信息，来路无关。

三条全中，心法就一句话：把每个子问题的答案存进表里，按规模从小到大填，填到最后就是原问题的答案。递归加缓存（记忆化）是自顶向下的写法；循环填表是自底向上的写法，后者没有递归开销、边界更直观，工程上更常用。两种写法的取舍有句口诀：转移关系还想不清楚时先写记忆化（照着递归自然生长，只加一行缓存），跑通后再翻译成自底向上的填表并顺手做空间优化——先对再快，别倒过来。

# 热身：爬楼梯——一步一格或两格，n 格有几种走法
def climb(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2                  # 地基：一格一种、两格两种
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]    # 转移：最后一步跨一格或两格
    return dp[n]

for n in (3, 4, 5):
    print(f"{n} 格楼梯：{climb(n)} 种走法")
# 输出：
# 3 格楼梯：3 种走法
# 4 格楼梯：5 种走法
# 5 格楼梯：8 种走法
# 转移方程就是斐波那契：dp[i] 只依赖前两格——这就是重叠子问题的最纯样本
​

主修功课：0-1 背包，填一张表看透一切

问题：三个物品，重量 1、3、4，价值 15、20、30，背包容量 4，每件至多带一件，求最大总价值。状态定义：dp[i][j] 表示"只考虑前 i 件、容量为 j 时的最大价值"。转移方程：第 i 件只有两种命运——

• 不带它：dp[i][j] = dp[i-1][j]；
• 带它（前提 j 装得下）：dp[i][j] = dp[i-1][j-w_i] + v_i。

取两者较大。

背包状态表的逐格填充

# 0-1 背包：完整状态表 + 答案
def knapsack(weights, values, cap):
    n = len(weights)
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):                    # 逐件考虑
        w, v = weights[i - 1], values[i - 1]
        for j in range(cap + 1):                 # 逐容量填表
            dp[i][j] = dp[i - 1][j]              # 不带第 i 件
            if j >= w:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v)   # 带它
    for row in dp:
        print(row)
    return dp[n][cap]

best = knapsack([1, 3, 4], [15, 20, 30], 4)
print("最大价值 =", best)
# 输出：
# [0, 0, 0, 0, 0]
# [0, 15, 15, 15, 15]
# [0, 15, 15, 20, 35]
# [0, 15, 15, 20, 35]
# 最大价值 = 35
​

表里的每个数字都能用上图复算：35 出现在第 2 行第 4 列，来源是第 1 行第 1 列的 15 加上第 2 件价值 20。时间 O(n·cap)、空间同阶——注意这里 cap 也进了复杂度（伪多项式），容量上百万时填表并不可行。

空间收缩：滚动数组

第 i 行只依赖第 i-1 行，整张表可以压成一行。但容量必须倒序枚举：正序会先更新小容量格子，再被同件物品"二次使用"（那成了无限件背包）；倒序保证每件物品只用一次：

# 滚动数组：一行搞定，容量倒序是生死线
def knapsack_1d(weights, values, cap):
    dp = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for j in range(cap, w - 1, -1):          # 倒序：防止本件被重复装
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[cap]

print("一维版答案 =", knapsack_1d([1, 3, 4], [15, 20, 30], 4))
# 输出：一维版答案 = 35
# 空间从 (物品数+1)×(容量+1) 压到 (容量+1) 个格子
​

⚠️ 常见坑：0-1 背包一维写成正序。正序枚举时 dp[j-w] 已被本件更新过，等于允许同一件带多次——答案变大且错。判断口诀：每件至多一次，容量倒序；每件可无限次，容量正序。

💡 关键直觉：动态规划 = 图论视角下的最短路。把每个状态当顶点、转移当边，填表就是按拓扑序求最短路（对照 4.5 节）。这个视角能解释为什么无后效性不可缺：环上的状态没有合法的填表顺序。

走火入魔：三个高频翻车点

翻车一：状态定义含糊。"dp[i] 是前 i 个的最优"与"dp[i] 是以第 i 个结尾的最优"是两个世界（后者如最长上升子序列）。定义里必须写清"以什么结尾/还剩什么"，转移才推得动。写代码前先用一句话把状态念出来。

**翻车二：初始化与答案错位。**求"恰好装满"的背包，dp[0] 初始化 0、其余初始化负无穷；求"不超过容量"的背包，全零初始化。混用两者是习题错误率的头部来源。

**翻车三：把所有问题都往 DP 上套。**子问题不重叠时（多数分治场景），DP 的表只是浪费内存；没有最优子结构时（某些带后效性的博弈问题），转移方程根本不成立。先验证三要素，再动笔。

本节要点回顾

• 三要素：最优子结构、重叠子问题、无后效性，缺一不可；三条全中才用填表；
• 四步流程：定义状态、写转移方程、定初始化、按依赖序填表；爬楼梯是最小完整样本；
• 0-1 背包：dp[i][j] 逐件逐容量填表，35 的来历每格可复算；时间空间 O(n·cap)，属伪多项式；
• 滚动数组压到一行，容量必须倒序枚举；正序即变成无限背包；
• 状态即顶点、转移即边：DP 是拓扑序下的最短路，无后效性就是"无环"。

一步一个脚印的填表之后，下一节反其道而行：每步只取眼前最好，赌它能通向全局最优——贪心。