数据结构与算法 / 系统课时
处理一维状态的滚动优化
处理一维状态的滚动优化
当一层 DP 只依赖上一层或更少的历史信息时,完整保存所有状态往往是浪费。滚动优化的核心不是单纯“把二维数组改成一维”,而是识别哪些旧状态仍会被读取,并安排更新顺序,避免新值提前覆盖它们。
学习目标
- 判断一个 DP 是否满足滚动压缩的依赖条件
- 区分“用临时变量滚动”和“原地覆盖一维数组”两类优化
- 根据依赖来源选择正序或倒序更新,避免读到已覆盖状态
先确认哪些历史状态还活着
如果当前状态只依赖前一层,那么更早的层在计算完成后就不会再被读取,可以释放。例如斐波那契型转移只需要最近两个值,用两个变量就足够。
另一类常见情况是二维状态 dp[i][c] 只依赖上一层 dp[i - 1][...]。这时可以把“层”这一维压掉,只保留容量维 dp[c]。但一旦原地覆盖,同一个数组里会同时存在“上一层旧值”和“当前层新值”,更新方向就变成正确性的关键。
用 0/1 背包看清覆盖风险
0/1 背包中,每件物品最多使用一次。二维转移可写成:
压成一维后,目标形式是 dp[c] = max(dp[c], dp[c - w] + v)。为了让右侧的 dp[c - w] 仍代表“上一层”,容量必须从大到小更新。

这条规则不是“背包题必须倒序”的口诀,而是由依赖层决定的:如果当前更新必须读取上一层旧值,就要避免先覆盖它;如果题目允许同一物品重复使用,更新方向可能恰好相反。
写出正确的一维实现
下面的完整程序求容量为 5 时的 0/1 背包最大价值。内层循环倒序遍历容量,因此一件物品在同一轮最多只会被使用一次。
def knapsack_01(weights, values, capacity):
dp = [0] * (capacity + 1)
for weight, value in zip(weights, values):
# 倒序保证 dp[c - weight] 仍是处理当前物品前的旧状态。
for c in range(capacity, weight - 1, -1):
dp[c] = max(dp[c], dp[c - weight] + value)
return dp[capacity]
if __name__ == "__main__":
weights = [2, 3, 4]
values = [4, 5, 6]
print(knapsack_01(weights, values, 5))预期输出
9这里选择重量 2 和 3 的两件物品,总价值为 9。时间复杂度仍是 ,其中 是物品数、 是容量;空间从二维实现的 降为 。
判断更新方向的通用方法
不要先问“这类题通常正序还是倒序”,而要先问“右侧读取的状态属于哪一层”。如果右侧必须是上一层旧值,就让遍历顺序避开已经被当前层覆盖的位置;如果右侧允许使用当前层刚更新出的值,就可以沿着依赖传播方向更新。
因此,滚动优化真正压缩的是“已经不会再被使用的历史层”。空间减少只是结果,保持依赖语义不变才是正确性的前提。