什么时候可以使用滚动数组优化？

Floyd

求全源最短路最常用的就是Floyd算法，代码十分简单，仅需三个for循环。

for(k = 1; k <= n; k++)
  for(i = 1; i <= n; i++)
    for(j = 1; j <= n; j++)
      f[i][j] = min(f[i][j], f[i][k] + f[k][j]);

但是，Floyd算法为什么能这么写。为什么枚举k就能算出两点间的最短路？

其实，这段代码是经过所谓滚动数组优化的版本，它原本应该是这样的。

for (k = 1; k <= n; k++)
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k] + f[k-1][k][j]);

f[k][i][j]表示只经过编号小于k的节点，从i到j的最短路。

这显然是一个动态规划问题

初始状态：
f[0][i][j] = inf (i != j)
f[0][i][i] = 0

转移方程：
f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k] + f[k-1][k][j])

因为加入新的节点k之后，新的最短路要么经过k，要么不经过k，对两种情况取min即可。

滚动数组优化后的转移方程如下：

f[i][j] = min(f[i][j], f[i][k] + f[k][j])

若使用滚动数组优化，去掉第一维，f[i][k]和f[k][j]有可能在f[i][j]被更新之前被更新。要证明优化后方程的正确性，则只需证明无论使用更新过的f[…][…]还是更新前的f[…][…]，转移方程得到的结果都是正确的。

原始转移方程等号右边有三个数f[k-1][i][j]、f[k-1][i][k]和f[k-1][k][j]

对于f[k-1][i][j]，它的值就是优化后f[i][j]被更新前的值

而对于f[k-1][i][k]，因为f[k-1][k][k] = 0，所以有f[k][i][k] = min(f[k-1][i][k], f[k-1][i][k] + f[k-1][k][k]) = f[k-1][i][k]

同理f[k][k][j] = f[k-1][k][j]

分别替换原来的三个数就搞定了。

这个例子中能使用滚动数组优化，是因为更新后的状态也能用来转移

滚动数组优化最常见的应用其实是背包dp

以最简单的0-1背包问题为例，有n个物品价值v_i，重量w_i，每个物品可以选一件或不选。求选取物品总重量不超过背包容量m的条件下，所选物品价值总和的最大值。

f[i][j]表示只考虑前i件物品，使用j容量时的答案。

显然有：f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i])

1
2
3

for(int i = 1; i <= n; ++i)
  for(int j = 0; j <= m; ++j)
    f[i][j] = (j >= w[i] ? max(f[i-1][j], f[i-1][j-w[i]] + v[i]) : f[i-1][j]);

为什么这里可以去掉第一维变成 f[j] = max(f[j], f[j-w[i]] + v[i])，原因与floyd的例子有所不同。

优化后j需要反向枚举

1
2
3

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]);

这样才能保证计算f[j]时，f[j-w[i]]未被更新。

这样可以按照一定的顺序，避免使用更新后的变量

如果要使用滚动数组优化，只需满足以下条件之一：