hdu 1513 && 1159 poj Palindrome (dp, 滚动数组， LCS)

以前做过的一道题，今天又加了一种方法整理了一下。。。。。

题意：给出一个字符串，问要将这个字符串变成回文串要添加最少几个字符。

方法一：

将该字符串与其反转求一次LCS，然后所求就是n减去最长公共子串的长度。

额，，这个思路还是不是很好想。

LCS:

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 const int maxn = 5000+10;
 6 char s1[maxn], s2[maxn];
 7 int d[2][maxn], n;
 8 int mmin(int a,int b)
 9 {
10     return a>b?b:a;
11 }
12 int mmax(int a, int b)
13 {
14     return a<b?b:a;
15 }
16 void Lcs()
17 {
18     int i, j;
19     for(i = 1; i <= n; i++)
20         for(j = 1; j <= n; j++)
21             if(s1[i] == s2[j])
22                 d[i%2][j] = d[(i-1)%2][j-1] + 1;
23             else
24                 d[i%2][j] = mmax(d[(i-1)%2][j], d[(i%2)][j-1]);
25 }
26 int main()
27 {
28     int i;
29     while(cin>>n)
30     {
31         memset(d, 0, sizeof(d));
32         for(i=1; i<=n; i++)
33             cin>>s1[i];
34         for(i = n; i >=1; i--)
35             s2[i] = s1[n-i+1];
36         Lcs();
37         cout<<n-d[n%2][n]<<endl;
38     }
39     return 0;
40 }

方法二：

这个是discuss里的方法。

设ch[1]..ch[n]表示字符串1至n位，i为左游标，j为右游标 ，则i从n递减，j从i开始递增。
min[i][j]表示i和j之间至少需要插入多少个字符才能对称,初始置全0 ,我们最终需要得到的值是min[1][n].
则
if(ch[i]==ch[j])                                    //如果两个游标所指字符相同，向中间缩小范围
    min[i][j]=min[i+1][j-1];
else
     min[i][j] = 1 +  （min[i+1][j]和min[i][j-1]中的较小值）;     //如果不同，典型的状态转换方程

下面这个代码是用的short int d[5000][5000]

在poj 可以水过，但是在hdu还超内存，，所有需要用滚动数组来节省内存。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 
 6 int mmin(int a,int b)
 7 {
 8     return a>b?b:a;
 9 }
10 short int d[5010][5010];
11 int main()
12 {
13     int n,i,j;
14     char s[5010];
15     memset(d,0,sizeof(d));
16     cin>>n;
17     for(i=1; i<=n; i++)
18     cin>>s[i];
19     for(i=n; i>=1; i--)
20     for(j=i+1; j<=n; j++)
21     if(s[i]==s[j])
22     d[i][j]=d[i+1][j-1];
23     else
24     d[i][j]=mmin(d[i+1][j],d[i][j-1])+1;
25 
26     cout<<d[1][n]<<endl;
27     return 0;
28 }

因为d[i][j] 算的时候只是与 d[i+1][j] 和 d[i][j+1]有关，所有可以开一个d[2][5000]的数组。

滚动数组节省内存：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 
 6 int mmin(int a,int b)
 7 {
 8     return a>b?b:a;
 9 }
10 int d[2][5010];
11 int main()
12 {
13     int n,i,j;
14     char s[5010];
15     while(cin>>n)
16     {
17         memset(d, 0, sizeof(d));
18         for(i=1; i<=n; i++)
19             cin>>s[i];
20 
21         for(i=n; i>=1; i--)
22             for(j=i+1; j<=n; j++)
23                 if(s[i]==s[j])
24                     d[i%2][j]=d[(i+1)%2][j-1];
25                 else
26                     d[i%2][j]=mmin(d[(i+1)%2][j],d[i%2][j-1])+1;
27 
28         cout<<d[1][n]<<endl;
29     }
30     return 0;
31 }

贴一下别人博客里的滚动数组的介绍：

滚动数组举个简单的例子：
int i,d[100];
d[0]=1;d[1]=1;
for(i=2;i<100;i++)
d[i]=d[i-1]+d[i-2];
printf("%d",d[99]);
上面这个循环d[i]只需要解集中的前2个解d[i-1]和d[i-2];
为了节约空间用滚动数组的方法

int d[3];
d[0]=1;d[1]=1;
for(i=2;i<100;i++)
d[i%3]=d[(i-1)%3]+d[(i-2)%3];
printf("%d",d[99%3]);

注意上面的运算，我们只留了最近的3个解，数组好象在“滚动?一样，所以叫滚动数组

对于二维数组也可以用这种方法例如：
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];

滚动数组实际是一种节约空间的办法，时间上没什么优势，多用于DP中，举个例子先：
一个DP，平常如果需要1000×1000的空间，其实根据DP的特点，能以2×1000的空间解决问题，并且通过滚动，获得和1000×1000一样的效果。

hdu 1513 && 1159 poj Palindrome (dp, 滚动数组， LCS)

推荐阅读