数据结构与算法 / 系统课时
定位遍历顺序与转移覆盖错误
定位遍历顺序与转移覆盖错误
动态规划压缩空间后,很多错误并不是公式写错,而是更新顺序让新值覆盖了仍要使用的旧值。本篇从“当前状态到底应该读取上一阶段还是当前阶段数据”出发,统一排查 0/1 背包、滚动数组和区间 DP 的遍历方向问题。
学习目标
- 能根据状态依赖判断循环应该正序、逆序还是按区间长度推进。
- 能识别滚动数组中“旧阶段数据被当前阶段提前覆盖”的错误。
- 能用最小样例和依赖关系验证遍历顺序是否保持原转移语义。
先问清楚读取的是哪一阶段
二维 DP 压成一维后,下标没变,但同一个数组槽位会先后代表不同阶段。此时必须给每次读取贴上“旧”或“新”的标签。
以 0/1 背包为例,二维转移可以写成 dp[i][c] = max(dp[i-1][c], dp[i-1][c-w] + v)。选第 i 个物品时,两个来源都必须来自上一行。压成一维后,如果容量从小到大更新,dp[c-w] 可能已经在本轮被改写,于是同一件物品会被重复使用。
相反,完全背包允许同一件物品重复选择,因此恰好需要让 dp[c-w] 看到本轮更新后的值。遍历方向不是背诵规则,而是由“允许读旧值还是新值”决定。

用最小反例检查 0/1 背包
只用两个物品就足以暴露方向错误:重量和价值分别为 (2,3)、(3,4),背包容量为 4。正确答案是 4;如果把容量正序更新,第一个物品会在同一轮被“再次读取”,错误地得到价值 6。
def knapsack_desc(items, capacity):
dp = [0] * (capacity + 1)
for weight, value in items:
# 0/1 背包必须逆序,保证读取的是加入当前物品之前的旧状态
for c in range(capacity, weight - 1, -1):
dp[c] = max(dp[c], dp[c - weight] + value)
return dp
def knapsack_asc(items, capacity):
dp = [0] * (capacity + 1)
for weight, value in items:
# 这是故意保留的错误版本,用于展示覆盖问题
for c in range(weight, capacity + 1):
dp[c] = max(dp[c], dp[c - weight] + value)
return dp
items = [(2, 3), (3, 4)]
capacity = 4
correct = knapsack_desc(items, capacity)
wrong = knapsack_asc(items, capacity)
print("descending:", correct, "answer=", correct[capacity])
print("ascending :", wrong, "answer=", wrong[capacity])预期输出:
descending: [0, 0, 3, 4, 4] answer= 4
ascending : [0, 0, 3, 4, 6] answer= 6错误值 6 等价于把重量 2、价值 3 的物品用了两次。这个反例直接证明:正序遍历已经改变了原二维转移的语义,而不是“某个测试数据刚好不通过”。
排查滚动数组的覆盖时机
滚动数组的核心问题与背包相同:一个槽位什么时候从旧阶段变成新阶段。调试时可以暂时取消压缩,恢复二维数组;如果二维版本正确、一维或两行滚动版本错误,优先检查覆盖顺序,而不是重新怀疑状态定义。
对于只依赖上一行同列和左上角的转移,若改成一维,通常需要额外保存“左上角旧值”。若直接更新 dp[j] 后再把它当作旧值使用,就会把当前行数据误传到后续状态。
区间 DP 要让小区间先完成
区间 DP 的典型状态 dp[l][r] 往往依赖更短的区间,例如 dp[l][k] 与 dp[k+1][r]。因此外层通常按区间长度从小到大遍历,而不是简单按 l、r 的自然顺序扫描。
判断方法仍然只有一个:在计算 dp[l][r] 之前,它依赖的所有状态是否已经确定。如果某个依赖区间与当前区间同长或更长,就要重新检查转移;如果依赖更短但程序还没算到,则遍历顺序错误。
实际排查时,可以给每个状态记录“首次写入时刻”。一旦发现当前状态读取了尚未计算的默认值,或读取了本轮刚覆盖的新值,就已经找到顺序问题。最终要验证的不是“循环看起来像模板”,而是每条依赖边都从已完成状态指向当前状态。