动态规划空间优化滚动数组不是删一维那么简单一、空间优化先看依赖关系动态规划写出二维数组后经常会想优化空间。很多题解会说“发现只依赖上一行所以可以滚动数组”。这句话没错但太省略。真正要看的是状态依赖方向、更新顺序和是否会覆盖还没用到的值。空间优化不能只追求少开数组。如果为了省一点内存把状态转移写得难以理解或者引入覆盖错误就得不偿失。先写对再优化优化后要重新证明。二、依赖图决定能不能滚动flowchart LR A[dp i-1 j] -- C[dp i j] B[dp i j-1] -- C D[dp i-1 j-1] -- C如果当前状态只依赖上一行可以用两行滚动。如果还依赖当前行左侧就要注意 j 的遍历方向。01 背包从大到小遍历完全背包从小到大遍历原因就在覆盖关系。不要机械记忆遍历方向。每次都画出依赖当前值计算时需要的是旧值还是新值。需要旧值就不能提前覆盖需要新值就必须允许同一轮更新。三、代码要保留语义def knapsack_01(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]01 背包倒序遍历是为了保证每个物品只使用一次。dp[c - w]必须来自上一轮物品而不是当前物品已经更新后的值。这个解释比“模板要求倒序”更重要。def knapsack_complete(weights, values, capacity): dp [0] * (capacity 1) for w, v in zip(weights, values): for c in range(w, capacity 1): dp[c] max(dp[c], dp[c - w] v) return dp[capacity]完全背包正序遍历是因为同一物品可以重复使用。此时使用当前轮已经更新过的dp[c - w]是符合题意的。四、优化后要重新验证边界空间优化可能改变初始化语义。二维 dp 里第一行、第一列很清楚压成一维后初始值就更容易写错。尤其是计数类、最小值类和不可达状态类题目默认 0 不一定合适。题解中要说明优化前后的状态含义是否变化。若一维dp[j]表示“处理到当前物品后的结果”就要明确每轮循环结束后的不变量。没有不变量滚动数组很容易变成玄学。空间优化还会影响路径还原。如果题目只要求最优值一维数组通常够用如果要求输出具体方案压缩后可能丢失决策信息。可以额外保存 parent 指针或者放弃部分空间优化。题解要说明目标是求值还是求方案。计数类 dp 也要特别小心。比如组合数和排列数外层循环顺序不同含义就不同。空间压缩后循环顺序同时承担“是否允许重复”和“顺序是否敏感”的语义。只背模板很容易把组合题写成排列题。最后优化前后要用同一批测试用例对比。先保留二维版本作为参考实现再验证一维版本输出一致。这个步骤很朴素但能抓住很多覆盖错误。五、总结动态规划空间优化要先分析依赖关系再决定滚动数组和遍历方向。优化后必须重新检查初始化和不变量。滚动数组不是删掉一维那么简单。它本质上是在用更新顺序维护原二维状态的语义。