本文共 913 字，大约阅读时间需要 3 分钟。

先占个坑吧...还有，csdn里我打这么多空格好难受- -（才不会说我是写字板里粘过来的）

滚动数组的作用在于优化空间，主要应用在递推或动态规划中（如01背包问题）。因为DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。

出处(星号)https://blog.csdn.net/geekdoe/article/details/50497607是啊是啊!想想之前背包里面前面的似乎是更新过就用不到了(当他被更新了之后)是啊是啊!斐波那契这个是递增的!(优化空间..时间没啥用所以)常常用于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<n，0<k<=10;n <= 100000000;显然缩不成一维,正常我们应该开一个DP[100000005][11]的数组，结果很明显，超内存，其实我们只要开DP[3][11]就够了DP[i%3][j]由DP[(i - 1)%3][k]和DP[(i - 2)%3][k]决定，空间复杂度差别巨大。

(讲的好清楚啊!!!所以贴一下..)

原网站找不到了... 甩两张图先占个坑走人- --

还会回来的!...

我只是占个坑而已!!!(怕之后又忘了所以聊胜于无吧= =)