https://www.bilibili.com/video/av371396684/
滚动数组是DP中的一种编程思想。简单的理解就是让数组滚动起来，每次都使用固定的几个存储空间，来达到压缩，节省存储空间的作用。起到优化空间，主要应用在递推或动态规划中（如01背包问题）。因为DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。
当然是用时间去换空间的
举个简单的例子
斐波那契数列：
#include<stdio.h>
int main()
{
int i;
long long d[80];
d[0]=1;
d[1]=1;
for(i=2;i<80;i++)
{
d[i]=d[i-1]+d[i-2];
}
printf("%lld
",d[79]);
return 0;
上面这个循环d[i]只依赖于前两个数据d[i - 1]和d[i - 2]; 为了节约空间用滚动数组的做法。
#include<stdio.h>
int main()
{
int i;
long long d[3];
d[1]=1;
d[2]=1;
for(i=2;i<80;i++)
{
d[0]=d[1];
d[1]=d[2];
d[2]=d[0]+d[1];
}
printf("%lld
",d[2]);
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
",d[79%3]);
return 0;
二维数组举例
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];//或者 d[i &1 ][j] = d[(i - 1)&1 ][j] + d[i &1][j - 1];
其实还可以改为：
for(i = 1; i < 100; i++)
for(j = 0; j < 100; j++)
d[j] = d[j] + d[j - 1];//
参考：
https://blog.csdn.net/weixin_40295575/article/details/80181756
https://leetcode-cn.com/problems/unique-paths/solution/bu-tong-lu-jing-by-leetcode-solution-hzjf/
为什么官方的代码这么难理解？
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m,vector<int>(n,1));
for(int i = 1;i < m;i++)
{
for(int j = 1;j < n;j++)
{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
内存优化后：
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> pre(n,1),cur(n,1);
for(int i = 1;i < m;i++)
{
for(int j = 1;j < n;j++)
{
cur[j] = pre[j] + cur[j - 1];
}
swap(pre,cur);
}
return pre[n-1];
}
};
再进一步优化：
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> dp(n,1);
for(int i = 1;i < m;i++)
{
for(int j = 1;j < n;j++)
{
dp[j] += dp[j-1];
}
}
return dp[n-1];
}
};
dp三角形金字塔中滚动数组；