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

删除状态中的冗余维度

删除状态中的冗余维度

动态规划的空间复杂度往往不是由题目规模本身决定,而是由状态里保留了多少历史决定。本篇用 0/1 背包说明如何判断某一维是否只代表计算阶段,并把二维状态压缩为一维,同时保留完全相同的转移语义。

学习目标

  • 判断状态维度是否会影响未来转移
  • 把只依赖上一阶段的二维 DP 压缩为滚动一维数组
  • 理解压缩后遍历方向为什么可能改变答案

先问这一维是否真的属于状态

设 0/1 背包中 dp[i][c] 表示“只看前 i 个物品、容量为 c 时的最大价值”。这里的 c 会直接影响后续选择,而 i 更多是在描述当前处理到了哪个阶段。

如果第 i 行只依赖第 i - 1 行,那么计算完新一行后,更早的行不会再被访问。此时 i 不是必须长期保存的状态维度,而是可以由循环顺序表达的阶段。

判断某一维能否删除,可以依次检查:未来转移是否会访问更早阶段、是否需要从多个历史阶段同时取值、压缩后读写是否会互相覆盖。只有这三项都安全,删维才不改变语义。

二维背包状态压缩为一维滚动数组

用依赖关系删除阶段维度

下面的完整示例同时实现二维版本和一维压缩版本。两者使用同一组物品,最后用断言验证结果一致。

python
def knapsack_2d(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        w = weights[i - 1]
        v = values[i - 1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i - 1][c]
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)

    return dp[n][capacity]


def knapsack_1d(weights, values, capacity):
    dp = [0] * (capacity + 1)

    for w, v in zip(weights, values):
        # 倒序保证 dp[c - w] 仍来自上一阶段。
        for c in range(capacity, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)

    return dp[capacity]


weights = [2, 3, 4]
values = [4, 5, 6]
capacity = 5

full = knapsack_2d(weights, values, capacity)
compressed = knapsack_1d(weights, values, capacity)

assert full == compressed
print(f'full={full}')
print(f'compressed={compressed}')

预期输出

text
full=9
compressed=9

二维版本需要保存 (n + 1) × (capacity + 1) 个状态,一维版本只保留 capacity + 1 个状态,因此空间复杂度从 O(nC) 降为 O(C),时间复杂度仍为 O(nC)。优化的本质不是少开一个数组,而是确认被删除的维度不会再参与未来决策。

压缩后最容易错的是覆盖顺序

一维数组同时承担上一阶段和当前阶段的存储职责,因此遍历方向成为状态语义的一部分。0/1 背包要求每个物品最多使用一次,所以容量必须从大到小更新。

如果改成从小到大,更新较大容量时可能读到本轮刚刚写入的 dp[c - w],相当于同一个物品在当前阶段被重复选择,问题就悄悄变成了完全背包。

什么时候不能直接删维

如果 dp[i] 同时依赖 dp[i - 1]、dp[i - 2],可以保留有限个滚动层;如果未来转移需要任意历史阶段,或最终还要回溯完整选择路径,就不能只留下当前层。

因此,删除冗余维度的标准不是这一维看起来像序号,而是它是否携带未来仍需读取的信息。先画清依赖,再决定保留几层,通常比直接套滚动数组更可靠。

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

目录与阅读设置

阅读设置

17

记录一个想法

删除状态中的冗余维度

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

登录哪都通