如何滚动一个数组

Re:Linked

空间复杂度系列。

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

写在前面

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

狭义滚动数组

许多动态规划方程都形如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]。伪代码类似于:

1
2
3
4
5
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)),于是我们自然就可以使用:

1
2
3
4
5
6
bool T=0; //标记变量

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

T = !T; //啊哈!

更广义的滚动数组

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

1
2
3
4
5
6
7
8
9
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;