线性动态规划的空间压缩技巧
在竞赛或工程实践中，三维甚至更高维的 DP 往往带来内存与时间双重压力。下面用两道典型例题演示如何把 O(n³) 的状态压缩到 O(n²) 乃至 O(n)。
例题一：河上漂流
一条船初始位于距下游 d 米处，共有 t 秒，每秒可以选择：
- 消耗 1 点体力向前划 1 米；
- 不消耗体力，被水流冲回 1 米。
体力上限为 m，问 t 秒后体力恰好为 0 且未进入峡谷（距离 > 0）的方案数。
朴素思路
dp[i][j][k] // 第 i 秒，距下游 j 米，剩余体力 k 的方案数状态量 O(t·(d+m)·m) ≈ 3e10，显然爆炸。
关键观察
设共划了 x 次，则后退了 t-x 次，最终坐标
d + x - (t - x) = d + 2x - t
要满足 d + 2x - t > 0，且 x ≤ m。因此坐标 j 可由 x 唯一确定，不必再存。
二维转移
f[i][j] // 前 i 秒已用 j 次体力，且船未掉下悬崖的方案数
转移：
f[i][j] = f[i-1][j] + f[i-1][j-1] // 后退 or 前进
答案：
x = m 时，若 d + 2x - t > 0，则累加 f[t][x]核心代码：
const int MOD = 1e9+7;
LL dp[3005][1505]; // t ≤ 3000, m ≤ 1500
int main() {
LL d, t, m; cin >> d >> t >> m;
dp[0][0] = 1;
for (int i = 1; i <= t; ++i)
for (int j = 0; j <= m; ++j) {
dp[i][j] = dp[i-1][j];
if (j) dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD;
}
LL ans = 0;
for (int x = 0; x <= m; ++x)
if (d + 2*x - t > 0) ans = (ans + dp[t][x]) % MOD;
cout << ans;
}例题二：模意义下的概率
给定 n 个数 ai 及其被选中的概率 pi，求选出的子集元素和 ≡ 0 (mod m) 的概率。
背包 DP
g[i][r] // 前 i 个数，和 mod m = r 的概率
g[i][r] = g[i-1][r]*(1-p[i]) + g[i-1][(r-a[i]%m+m)%m]*p[i]滚动数组
仅保留当前行即可：
LL pre[M], cur[M]; // M = 1010
pre[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int r = 0; r < m; ++r) {
int t = (r - a[i]%m + m) % m;
cur[r] = (pre[r]*(1 - p[i] + MOD) + pre[t]*p[i]) % MOD;
}
swap(pre, cur);
}
cout << pre[0];例题三：2×n 网格刷漆
从任意格子出发，每次只能走到相邻未涂色格子，求涂满 2×n 网格的方案数。
设
f[i]：涂满前 i 列且回到起点的方案数；g[i]：涂满前 i 列且停在另一行的方案数。
递推：
g[i] = 2 * g[i-1] % MOD; f[i] = (g[i] + 2*f[i-1] + 4*f[i-2]) % MOD;
总答案 = 4·f[n] + 4·Σi=2..n-1 (f[i-1]·g[n-i+1] + f[n-i]·g[i])
完整实现：
const int MOD = 1e9+7;
LL f[1010], g[1010];
int main() {
int n; cin >> n;
g[1] = 1; g[2] = 2;
f[1] = 1; f[2] = 6;
for (int i = 3; i <= n; ++i) {
g[i] = g[i-1]*2 % MOD;
f[i] = (g[i] + 2*f[i-1] + 4*f[i-2]) % MOD;
}
LL ans = 4*f[n] % MOD;
for (int i = 2; i < n; ++i)
ans = (ans + 4*(f[i-1]*g[n-i+1] + f[n-i]*g[i])) % MOD;
cout << ans;
}小结
高维 DP 的压缩通常遵循两条路线：
- 发现某一维可由其余维度唯一确定，直接剔除；
- 若维度仅用于"继承上一阶段"，则使用滚动数组或swap 技巧将 O(n) 空间降至 O(1)。
