以前做过的一道题， 今天又加了一种方法 整理了一下。。。。。
题意：给出一个字符串，问要将这个字符串变成回文串要添加最少几个字符。
方法一：
将该字符串与其反转求一次LCS，然后所求就是n减去 最长公共子串的长度。
额，，这个思路还是不是很好想。
LCS:
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = +;
char s1[maxn], s2[maxn];
int d[][maxn], n;
int mmin(int a,int b)
{
return a>b?b:a;
}
int mmax(int a, int b)
{
return a<b?b:a;
}
void Lcs()
{
int i, j;
for(i = ; i <= n; i++)
for(j = ; j <= n; j++)
if(s1[i] == s2[j])
d[i%][j] = d[(i-)%][j-] + ;
else
d[i%][j] = mmax(d[(i-)%][j], d[(i%)][j-]);
}
int main()
{
int i;
while(cin>>n)
{
memset(d, , sizeof(d));
for(i=; i<=n; i++)
cin>>s1[i];
for(i = n; i >=; i--)
s2[i] = s1[n-i+];
Lcs();
cout<<n-d[n%][n]<<endl;
}
return ;
}
方法二：
这个是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还超内存，，所有需要用滚动数组来 节省内存。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; int mmin(int a,int b)
{
return a>b?b:a;
}
short int d[][];
int main()
{
int n,i,j;
char s[];
memset(d,,sizeof(d));
cin>>n;
for(i=; i<=n; i++)
cin>>s[i];
for(i=n; i>=; i--)
for(j=i+; j<=n; j++)
if(s[i]==s[j])
d[i][j]=d[i+][j-];
else
d[i][j]=mmin(d[i+][j],d[i][j-])+; cout<<d[][n]<<endl;
return ;
}
因为d[i][j] 算的时候只是与 d[i+1][j] 和 d[i][j+1]有关，所有可以开一个d[2][5000]的数组。
滚动数组节省内存：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; int mmin(int a,int b)
{
return a>b?b:a;
}
int d[][];
int main()
{
int n,i,j;
char s[];
while(cin>>n)
{
memset(d, , sizeof(d));
for(i=; i<=n; i++)
cin>>s[i]; for(i=n; i>=; i--)
for(j=i+; j<=n; j++)
if(s[i]==s[j])
d[i%][j]=d[(i+)%][j-];
else
d[i%][j]=mmin(d[(i+)%][j],d[i%][j-])+; cout<<d[][n]<<endl;
}
return ;
}
贴一下别人博客里的滚动数组的介绍：
滚动数组 举个简单的例子：
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一样的效果。