滚动数组[转载]

利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。不过经常还是用在DP题目中,因为DP题目是一个自下而上的扩展过程,我们常常用到是连续的解,前面的解往往舍弃!所以用滚动数组可以说是很有必要的。

滚动数组 举个简单的例子:

1
2
3
4
5
6
int i, d[100];
d[0] = 1;
d[1] = 1;
for (i = 2; i < 100; i++)
    d[i] = d[i - 1] + d[i - 2];
printf("%d", d[99]);

上面这个循环d[i]只依赖于前两个数据d[i – 1]和d[i – 2];
为了节约空间用滚动数组的做法:

1
2
3
4
5
6
int d[3];
d[0] = 1;
d[1] = 1;
for (i = 2; i < 100; i++)
    d[i % 3] = d[(i - 1) % 3] + d[(i - 2) % 3];
printf("%d", d[99 % 3]);

注意上面的取余运算,我们成功地只保留了需要的最后3个解,数组好象在“滚动”一样,所以叫滚动数组。

//DP
对于二维也可以用(代码可能不太正确和完善,但是可以理解例子):

1
2
3
4
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];
运用滚动数组

1
2
3
4
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];

滚动数组实际是一种节省空间的办法,时间上没啥优势,多用于DP中,举个

例子吧:

一个DP,平常如果需要1000×1000的空间,其实根据DP的无后效性,可以开成2×1000,然后通过滚动,获得和1000×1000一样的效果。滚动数组常用于DP之中,在DP过程中,我们在由一个状态转向另一个状态时,很可能之前存储的某些状态信息就已经无用了,例如在01背包问题中,从理解角度讲我们应开DP[i][j]的二维数组,第一维我们存处理到第几个物品,也就是阶段了,第二维存储容量,但是我们获得DP[i],只需使用DP[i – 1]的信息,DP[i – k],k>1都成了无用空间,因此我们可以将数组开成一维就行,迭代更新数组中内容,滚动数组也是这个原理,目的也一样,不过这时候的问题常常是不可能缩成一维的了,比如一个DP[i][j]需要由DP[i – 1 ][k],DP[i – 2][k]决定,i

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《滚动数组[转载]》有14个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注