2023年8月1日发(作者：)

滚动数组---动态规划思想滚动数组—动态规划思想滚动数组是DP中的⼀种编程思想。简单的理解就是让数组滚动起来，每次都使⽤固定的⼏个存储空间，来达到压缩，节省存储空间的作⽤。起到优化空间，主要应⽤在递推或动态规划中（如01背包问题）。因为DP题⽬是⼀个⾃底向上的扩展过程，我们常常需要⽤到的是连续的解，前⾯的解往往可以舍去。所以⽤滚动数组优化是很有效的。利⽤滚动数组的话在N很⼤的情况下可以达到压缩存储的作⽤。当然是⽤时间去换空间的在斐波那契数列中#includeint 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("%lldn",d[79]); return 0;}上⾯这个循环d[i]只依赖于前两个数据d[i - 1]和d[i - 2]; 为了节约空间⽤滚动数组的做法，可以将整个dp数组压缩成dp[3]#includeint 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("%lldn",d[2]); return 0;}滚动数组在DP中能起很⼤作⽤尤其是当原本需要申请得内存⼤⼩很⼤得情况下滚动数组在回⽂串中的应⽤本⽂作者： RioTian

2023年8月1日发(作者：)

滚动数组---动态规划思想滚动数组—动态规划思想滚动数组是DP中的⼀种编程思想。简单的理解就是让数组滚动起来，每次都使⽤固定的⼏个存储空间，来达到压缩，节省存储空间的作⽤。起到优化空间，主要应⽤在递推或动态规划中（如01背包问题）。因为DP题⽬是⼀个⾃底向上的扩展过程，我们常常需要⽤到的是连续的解，前⾯的解往往可以舍去。所以⽤滚动数组优化是很有效的。利⽤滚动数组的话在N很⼤的情况下可以达到压缩存储的作⽤。当然是⽤时间去换空间的在斐波那契数列中#includeint 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("%lldn",d[79]); return 0;}上⾯这个循环d[i]只依赖于前两个数据d[i - 1]和d[i - 2]; 为了节约空间⽤滚动数组的做法，可以将整个dp数组压缩成dp[3]#includeint 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("%lldn",d[2]); return 0;}滚动数组在DP中能起很⼤作⽤尤其是当原本需要申请得内存⼤⼩很⼤得情况下滚动数组在回⽂串中的应⽤本⽂作者： RioTian