本文主要介绍一个十分实用的小技巧——滚动数组。它常被用来完成常数优化和减少代码量，且滚动数组思想是一种常见的动态规划优化方法。

假设有如下状态转移方程：

            dp[i][j] = max(dp[i-1][j+1], dp[i-1][j-1]);​

按照该状态转移方程，我们可以用二维数组保存其状态值，通过如下代码片段完成其状态的转移（这里仅做说明，不考虑边界情况）：

for(int i = 1; i <= n; i++){
	for(int j = 1; j <= m; j++){
		dp[i][j] = max(dp[i-1][j+1], dp[i-1][j-1]);
	}
}
int ans = dp[n][m];

考虑到每次状态的转移仅与上一行有关（或以及本行已更新的部分），我们可以将二维数组优化到使用一维数组保存。如下：

for(int i = 1; i <= n; i++){
	for(int j = 1; j <= m; j++){
        buf[i] = max(dp[j+1], dp[j-1]);
    }
    for(int j = 1; j <= m; j++){
		dp[j] = buf[j];
    }
}
int ans = dp[m];

如该代码片段所示，我们将原本二维的状态空间优化到了一维，对应的我们需要在每次状态转移过后进行依次循环次数为m的赋值操作。该操作不仅增加了代码量，还增加了程序的耗时。于是我们使用滚动数组，对其再次进行优化：

定义大小为2*m的数组为其状态空间：

int dp[2][m];

初始状态保存在dp[0][i]中。

设定两个int类型指针

int *src; //源指针
int *des; //目的指针

由于初始状态保存在dp数组的第0行中，初始时

src = dp[1];
des = dp[0];

按照状态转移方程进行状态转移

for(int i = 1; i <= n; i++){
	swap(src, des); //交换源指针和目的指针
	for(int j = 1; j <= m; j++){
		des[j] = max(src[j+1], src[j-1]);
	}
}
int ans = des[m];

如代码所示，我们在每次循环进行状态转移之前交换源数组和目的数组的指针，使程序能够正确的从源数组中转移状态到目的数组中。当状态转移完成时，新得到状态保存于目的数组中，但它在下一次循环的状态转移中又将变为源数组，于是我们在下次状态转移开始前再次交换源数组和目的数组指针，这就是滚动数组的工作原理。

滚动数组这个技巧不仅优化了原始的状态空间，还减少了循环次数节约了程序运行时间，同时对代码量的缩减也有很好的效果，是一个值得学习的小技巧。