说来惭愧，我老早以前就学习了dp，可直到最近才知道滚动数组。
所以说，滚动数组是什么呢？
它是一种优化dp空间复杂度的思想。
在dp转移时，我们往往不需要之前推的所有的，而是只需要前一两个转移的。
我们以斐波那契数列为例，代码如下：
for(int i=2;i<100;i++) { d[i]=d[i-1]+d[i-2] }
printf("%d",d[99]);
可以发现，如果求解99位，那么需要使用将近快100个存储单元。
如果求解位数更多，那么空间就爆了。
那用滚动数组怎么优化呢？
for(int i=2;i<100;i++) { d[i%3]=d[(i-1)%3]+d[(i-2)%3]; } printf("%d",d[99%3]);
这里无论求多少个，只需要留出三个存储单元的位置即可。
可以发现，空间优化了很多，但时间没有优化，甚至会更差。
而且，滚动数组还会覆盖之前的解，所以不是所有dp都能这么优化。
原文：https://www.cnblogs.com/mxrmxr/p/9800604.html