空间复杂度系列。
滚动数组,用于动态规划的空间复杂度优化。
写在前面
在应用滚动数组前,确定你的动态规划不是以递归形式书写的。递归形式书写的动态规划,虽然可以通过数组保存状态,但由于它每次的请求都会查询到末尾(数个深度优先查询),我们不容易将它控制在较小的区间内,也就不太使用滚动数组。
狭义滚动数组
许多动态规划方程都形如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;