如何滚动一个数组

空间复杂度系列。

滚动数组，用于动态规划的空间复杂度优化。

写在前面

在应用滚动数组前，确定你的动态规划不是以递归形式书写的。递归形式书写的动态规划，虽然可以通过数组保存状态，但由于它每次的请求都会查询到末尾（数个深度优先查询），我们不容易将它控制在较小的区间内，也就不太使用滚动数组。

狭义滚动数组

许多动态规划方程都形如f[m][n]=k*f[m-1][n]+l*f[m-1][n']，即f[n]的值只与f[n-1]有关。在这些情况下，f[n]在第n+1次循环之后就不再被使用。显然这导致了空间的浪费。

解决方案是：在数组中只保存F[n]与F[n-1]。伪代码类似于：

for j= 1...Jn
F[i][j] = k*F[i-1][j]; //转移状态

for j= 1...Jn
F[i-1] = F[i]; //更新数组

这种方法其实可能反而更累（因为每次操作O(1)后需要拷贝整个数组O(j)），于是我们自然就可以使用：

bool T=0; //标记变量

for j= 1...Jn
F[T][j] = k*F[!T][j]; //转移状态

T = !T; //啊哈！

更广义的滚动数组

以上是狭义的滚动数组（ΔT=2）。当然也可以使用更大的滚动数组。例如炮兵阵地。

int T=0; //标记变量

for j= 1...Jn
if (T>0)
F[T][j] = k*F[T-1][j]; //转移状态
else F[T][j] = k*F[2][j]; //转移状态

if (T<2) T++;
else T=0;