《征服数据结构》滚动数组
摘要：
1，一维滚动数组的介绍
2，多维滚动数组的介绍
1，一维滚动数组的介绍
滚动数组不是一种数据结构，它是一种算法优化思想，滚动数组的作用在于优化空间，降低空间复杂度，每次使用固定的一些存储空间。
比如我们常见的斐波那契数列：f[n] = f[n – 1] + f[n – 2] ，普通的写法如下：
Java 代码：
// 1、2、3、5、8、13、21、34、……
private int fibonacci(int n) {// n > 0
if (n == 1 || n == 2)
return n;
int[] res = new int[n + 1];
res[0] = 1;
res[1] = 2;
for (int i = 2; i <= n; i++)
res[i] = res[i - 1] + res[i - 2];
return res[n];
}C++ 代码：
public:
// 1、2、3、5、8、13、21、34、……
int fibonacci(int n) {// n > 0
if (n == 1 || n == 2)
return n;
vector<int> res(n + 1);
res[0] = 1;
res[1] = 2;
for (int i = 2; i <= n; i++)
res[i] = res[i - 1] + res[i - 2];
return res[n];
}如下图所示，虽然定义一个很长的数组，但每次都用最近的 3 个，前面的都浪费了，所以我们可以使用滚动数组，只需要一个长度为 3 的数组即可。
Java 代码：