困难C++3 分钟1,103 字

滚动数组优化动态规划

当动态规划的状态只依赖前一层(或前几层)时,就可以用滚动数组​把空间复杂度从 O(n·m) 降到 O(m)。这是 GESP 七级明确要求掌握的空间优化技巧。

问题从哪里来

先看一维 DP 的经典例子:​爬楼梯​​。每次可以走 1 阶或 2 阶,问走到第 n 阶有多少种走法。

cpp
// 朴素写法:用数组保存所有状态
long long dp[100005];
dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= n; i++)
    dp[i] = dp[i-1] + dp[i-2];

这里 dp[i] 只用到 dp[i-1] 和 dp[i-2],前面所有状态算完就"没用了"。为一个只用一次的数组开出 100000 个位置,是浪费。

最简单的情况:只依赖两个值

直接用三个变量轮换:

cpp
long long a = 1, b = 1;   // a = dp[i-2], b = dp[i-1]
for (int i = 2; i <= n; i++) {
    long long c = a + b;  // c = dp[i]
    a = b;
    b = c;
}
cout << b;   // 答案 dp[n]

空间从 O(n) 变成 O(1)​​。

二维 DP 的滚动数组

更常见也更有价值的是二维情况。以 0/1 背包​为例:

f[i][j] = 前 i 个物品、容量 j 时的最大价值
f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i])

注意 f[i][j] 只用到了第 i-1 层。于是可以只保留两层:

cpp
int f[2][10005];
for (int i = 1; i <= n; i++) {
    int cur = i & 1, pre = (i - 1) & 1;   // 交替使用 0 和 1 两行
    for (int j = 0; j <= m; j++) {
        f[cur][j] = f[pre][j];
        if (j >= w[i])
            f[cur][j] = max(f[cur][j], f[pre][j-w[i]] + v[i]);
    }
}
cout << f[n & 1][m];

用 i & 1 或 i % 2 让两行交替使用,空间从 O(n·m) 降到 O(m)​​。

更进一步:压成一维

0/1 背包其实可以只用一个一维数组,只要倒序枚举容量​​:

cpp
int f[10005] = {0};
for (int i = 1; i <= n; i++)
    for (int j = m; j >= w[i]; j--)      // 关键:从大到小
        f[j] = max(f[j], f[j - w[i]] + v[i]);
cout << f[m];

为什么必须倒序?​ 因为 f[j] 需要用到"上一层"的 f[j - w[i]]。如果正序枚举,f[j - w[i]] 可能已经在本次循环中被更新过(变成"本层"的值),相当于同一个物品被重复放入,题目就从 0/1 背包变成了​完全背包​。倒序保证取到的永远是旧值。

如果题目本来就是完全背包(物品可以无限取),则应正序​枚举:

cpp
for (int j = w[i]; j <= m; j++)          // 正序 = 完全背包
    f[j] = max(f[j], f[j - w[i]] + v[i]);

什么时候可以用滚动数组

判断标准只有一条:​计算第 i 层时,是否只依赖第 i-1 层(或有限的最近几层)​​​。

DP 类型 是否可滚动 说明
线性 DP(斐波那契、爬楼梯) 可以 只依赖前 1~2 项
0/1 背包、完全背包 可以 只依赖上一层
二维网格路径数 可以 只依赖上一行
区间 DP 不可以 需要所有更短的区间,无法压缩
树形 DP 视情况 通常按子树合并,不需要滚动

二维网格的例子

题目​​:一个 n×m 的网格,从左上角走到右下角,每次只能向右或向下,求路径数。

cpp
// 朴素:f[i][j] 数组 n*m
// 滚动:只保留上一行
int prev[1005], cur[1005];
fill(prev, prev + m, 0);
prev[0] = 1;                       // 起点
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (i == 0 && j == 0) { cur[j] = 1; continue; }
        cur[j] = (i > 0 ? prev[j] : 0) + (j > 0 ? cur[j-1] : 0);
    }
    copy(cur, cur + m, prev);
}
cout << prev[m-1];

常见错误

  • 0/1 背包写成正序​​:结果变成"物品可重复取",答案偏大。
  • 滚动时忘记清空​​:多组测试数据时,cur 数组必须在使用前重置。
  • 误用到需要完整历史的状态​​:如区间 DP、需要回溯路径的 DP,压缩后会丢失信息。
  • 下标边界​​:(i-1) & 1 在 i = 0 时会越界,注意从 1 开始循环。

小结

滚动数组的核心思想是只保留计算下一层真正需要的状态​​。一维变量轮换用于只依赖前一两项的递推,双层交替用于依赖上一层的二维 DP,而 0/1 背包倒序 + 一维数组是最经典的应用。判断能否滚动,只看"是否只依赖上一次迭代的结果"。

同类知识点