滚动数组

oyangningtao · 发表于 2022-1-22 11:17:07

数组是最常用的数据结构之一，现在我们对数组的下标进行特殊处理，使每一次操作仅保留若干有用信息，新的元素不断循环刷新，看上去数组的空间被滚动地利用，此模型我们称其为滚动数组。其主要达到压缩存储的作用，一般常用在DP类题目中。因为DP题目是一个自下而上的扩展过程，我们常常用到是连续的解，而每次用到的只是解集中的最后几个解，所以以滚动数组形式能大大减少内存开支。

最典型的就是斐波那契数列，普通的求解方法不外乎就是用递推式f=f[i-1]+f[i-2]，但是这个如果数据量大的话会爆内存，而用滚动数组的方法可以用3个单位大小的空间求得解，这样就节省了很多的空间。

斐波那契数列普通解法：

#include<iostream>

#include<cstdio>

using namespace std;

int f[100];

int ff(int n)
{
f[0] = 0;
f[1] = 1;
f[2] = 1;
for(int i = 3; i <= n; ++i)
      f = f[i - 1] + f[i - 2];
return f[n];
}

int main()
{
int t, n;
scanf("%d", &t);
while(t--)
{
      scanf("%d", &n);
      printf("%d\n", ff(n));
}
return 0;
}

滚动数组解法：
#include<cstdio>
using namespace std;
int f[3];

int ff(int n)
{
f[1] = 0;
f[2] = 1;
for(int i = 2; i <= n; ++i)
{
      f[0] = f[1];
      f[1] = f[2];
      f[2] = f[0] + f[1];
}
return f[2];
}

int main()
{
int t, n;
scanf("%d", &t);
while(t--)
{
      scanf("%d", &n);
      printf("%d\n", ff(n));
}
return 0;

}

另一种表达形式：
#include<stdio.h>
int main()
{
int i;
long long d[3];
d[0] = 1;
d[1] = 1;
for(i=2;i<80;i++)
{
      d[i%3]=d[(i-1)%3]+d[(i-2)%3];
}
printf("%lld\n",d[79%3]);
return 0;
}

oyangningtao · 发表于 2022-1-22 11:17:27

二维数组举例

int i, j, d[100][100];

for(i = 1; i < 100; i++)

for(j = 0; j < 100; j++)

d[i][j] = d[i - 1][j] + d[i][j - 1];

上面的d[i][j]只依赖于d[i - 1][j], d[i][j - 1];

运用滚动数组：

int i, j, d[2][100];

for(i = 1; i < 100; i++)

for(j = 0; j < 100; j++)

d[i % 2][j] = d[(i - 1) % 2][j] + d[i % 2][j - 1];

滚动数组主要应用在递推或动态规划（如01背包问题）及状态压缩算法。