数据结构与算法 / 系统课时

处理一维状态的滚动优化

处理一维状态的滚动优化

当一层 DP 只依赖上一层或更少的历史信息时,完整保存所有状态往往是浪费。滚动优化的核心不是单纯“把二维数组改成一维”,而是识别哪些旧状态仍会被读取,并安排更新顺序,避免新值提前覆盖它们。

学习目标

  • 判断一个 DP 是否满足滚动压缩的依赖条件
  • 区分“用临时变量滚动”和“原地覆盖一维数组”两类优化
  • 根据依赖来源选择正序或倒序更新,避免读到已覆盖状态

先确认哪些历史状态还活着

如果当前状态只依赖前一层,那么更早的层在计算完成后就不会再被读取,可以释放。例如斐波那契型转移只需要最近两个值,用两个变量就足够。

另一类常见情况是二维状态 dp[i][c] 只依赖上一层 dp[i - 1][...]。这时可以把“层”这一维压掉,只保留容量维 dp[c]。但一旦原地覆盖,同一个数组里会同时存在“上一层旧值”和“当前层新值”,更新方向就变成正确性的关键。

用 0/1 背包看清覆盖风险

0/1 背包中,每件物品最多使用一次。二维转移可写成:

dp[i][c]=max⁡(dp[i−1][c], dp[i−1][c−wi]+vi)dp[i][c] = \max(dp[i-1][c],\ dp[i-1][c-w_i] + v_i)

压成一维后,目标形式是 dp[c] = max(dp[c], dp[c - w] + v)。为了让右侧的 dp[c - w] 仍代表“上一层”,容量必须从大到小更新。

0/1 背包滚动数组的更新方向

这条规则不是“背包题必须倒序”的口诀,而是由依赖层决定的:如果当前更新必须读取上一层旧值,就要避免先覆盖它;如果题目允许同一物品重复使用,更新方向可能恰好相反。

写出正确的一维实现

下面的完整程序求容量为 5 时的 0/1 背包最大价值。内层循环倒序遍历容量,因此一件物品在同一轮最多只会被使用一次。

python
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))

预期输出

text
9

这里选择重量 2 和 3 的两件物品,总价值为 9。时间复杂度仍是 O(nC)O(nC),其中 nn 是物品数、CC 是容量;空间从二维实现的 O(nC)O(nC) 降为 O(C)O(C)。

判断更新方向的通用方法

不要先问“这类题通常正序还是倒序”,而要先问“右侧读取的状态属于哪一层”。如果右侧必须是上一层旧值,就让遍历顺序避开已经被当前层覆盖的位置;如果右侧允许使用当前层刚更新出的值,就可以沿着依赖传播方向更新。

因此,滚动优化真正压缩的是“已经不会再被使用的历史层”。空间减少只是结果,保持依赖语义不变才是正确性的前提。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

处理一维状态的滚动优化

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通