使用范围:使用在递推或动态规划中
作用:节约空间
注意:时间上没什么优势
举例
1)作用在一维数组:
普通方法:
- int d[]=new int[100];
- d[0]=1;d[1]=1;
- for(int i=2;i<100;i++)
- {
- d[i]=d[i-1]+d[i-2]
- }
- System.out.printf("%d",d[99]);
上述方法使用100个空间(近似认为),
注意,上面这个循环d[i]只需要解集中的前2个解d[i-1]和d[i-2];为了节约空间用滚动数组的方法
使用滚动数组:
- int d[]=new int[3];
- d[0]=1;d[1]=1;
- for(int i=2;i<100;i++)
- {
- d[i%3]=d[(i-1)%3]+d[(i-2)%3];
- }
- System.out.printf("%d",d[99%3]);
注意上面的运算,我们只留了最近的3个解,数组好象在“滚动一样,所以叫滚动数组
2)作用在二维数组
举例
普通方法
- int d[]=new int[100][100];
- for(int i=1;i<100;i++)
- {
- for(int j=0;j<100;j++)
- {
- d[i][j]=d[i-1][j]+d[i][j-1];
- }
- }
上面的方法需要1000×1000的空间。
注意d[i][j]只依赖于d[i-1][j],d[i][j-1];可以使用滚动数组
使用滚动数组
- int d[][]=new int[2][100];
- for(int i=1;i<100;i++)
- {
- for(int j=0;j<100;j++)
- {
- d[i%2][j]=d[(i-1)%2][j]+d[i%2][j-1];
- }
- }
滚动数组使用2×1000的空间解决问题, 并且通过滚动,获得和1000×1000一样的效果
POJ1159(动态规划+滚动数组)
题意很明确,给你一个字符串,可在任意位置添加字符,最少再添加几个字符,可以使这个字符串成为回文字符串。
看到这道题,很熟悉,貌似以前做过,可就是想不起来解法,还是以前做的不认真。很惭愧,不过这次的解更优化。
解题思路:老实说,我从来没想到要用动态规划做。或许对动态规划了解不深吧,练得少。如果要是明确求两个字符串的最长公共子序列,我知道要用动态规划,这个老师也讲了多遍。万万没想到这道题就是变形后求原串与其逆串的最长公共子序列,然后用串长减去最长公共子序列的长度就是要添加的最少的字符数。(如果有人提醒我,我就知道怎么办了,可是在比赛的时候全靠自己。)另外还需注意的是字符串长度最长Max为5000,如果用数组maxlen[Max][Max],那么内存会超出。所以引进滚动数组,只需要定义maxlen[2][Max]就可以把问题解决了。(这是从队友那里学来的)首先初始化e=0;在每次行循环中用到e=1-e
就OK了。(这个很好用,大大减少的内存的占用。)
代码如下:
2 #include<cstring>
3 using namespace std;
4 #define Max 5005
5 char str1[Max],str2[Max];
6 int maxlen[2][Max];
7 int main()
8 {
9 int n,i,j;
10 while(cin>>n)
11 {
12 for(i=1;i<=n;i++)
13 cin>>str1[i];
14 str1[n+1]='\0';
15 for(i=1;i<=n;i++)//字符串str1的逆串
16 str2[i]=str1[n-i+1];
17 memset(maxlen,0,sizeof(maxlen));//初始化
18 int e=0;
19 for(i=1;i<=n;i++)//用动态规划求解
20 {
21 e=1-e;//用滚动数组,保证内存不会超出
22 for(j=0;j<=n;j++)
23 {
24 if(str1[i]==str2[j])
25 maxlen[e][j]=maxlen[1-e][j-1]+1;
26 else {
27 int len1=maxlen[e][j-1];
28 int len2=maxlen[1-e][j];
29 if(len1>len2) maxlen[e][j]=len1;
30 else maxlen[e][j]=len2;
31 }
32 }
33 }
34 cout<<n-maxlen[e][n]<<endl;
35 }
36 return 0;
37 }