DP与滚动数组-阿里云开发者社区

DP与滚动数组

2016-05-13 2591

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

转自：http://blog.csdn.net/niushuai666/article/details/6677982

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

一个简单的例子：

斐波那契数列：

一般代码：

[cpp]view plain copy 
   
 #include<iostream>   
 #include<cstdio>   
 using namespace std;   
 int Fib[25];   
    
 int fib(int n)   
 {   
     Fib[0] = 0;   
     Fib[1] = 1;   
     Fib[2] = 1;   
     for(int i = 3; i <= n; ++i)   
         Fib[i] = Fib[i - 1] + Fib[i - 2];   
     return Fib[n];   
 }   
    
 int main()   
 {   
     int ncase, n, ans;   
     scanf("%d", &ncase);   
     while(ncase--)   
     {   
         scanf("%d", &n);   
         ans = fib(n);   
         printf("%d\n", ans);   
     }   
     return 0;   
 }   

利用滚动数组优化后代码为：

[cpp]view plain copy 
   
     
 #include<cstdio>   
 using namespace std;   
 int Fib[3];   
    
 int fib(int n)   
 {   
     Fib[1] = 0;    
     Fib[2] = 1;   
     for(int i = 2; i <= n; ++i)   
     {   
         Fib[0] = Fib[1];    
         Fib[1] = Fib[2];   
         Fib[2] = Fib[0] + Fib[1];   
     }   
     return Fib[2];   
 }   
    
 int main()   
 {   
     int ncase, n, ans;   
     scanf("%d", &ncase);   
     while(ncase--)   
     {   
         scanf("%d", &n);   
         ans = fib(n);   
         printf("%d\n", ans);   
     }   
     return 0;   
 }           

滚动数组实际是一种节省空间的办法，时间上没啥优势，多用于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]决定，空间复杂度差别巨大。

文章标签：

存储

C++

DP与滚动数组

热门文章

最新文章

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

DP与滚动数组

热门文章

最新文章

相关电子书