困难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 背包倒序 + 一维数组是最经典的应用。判断能否滚动,只看"是否只依赖上一次迭代的结果"。