http://acm.hdu.edu.cn/showproblem.php?pid=1159
#include <cstdio>
#include<algorithm>
#include<string.h>
#include<cstring>
using namespace std;
const int maxn=1000+5;
char s1[maxn];
char s2[maxn];
int dp[maxn][maxn];
int main()
{
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
while(scanf("%s%s",s1,s2)==2)
{
int n=strlen(s1);
int m=strlen(s2);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++ )
{
for(int j=1;j<=m;j++)
{
if(s1[i-1]==s2[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;
}
else
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
printf("%d\n",dp[n][m]);
}
}
滚动数组优化
#include <cstdio>
#include<algorithm>
#include<string.h>
#include<cstring>
using namespace std;
const int maxn=1000+5;
char s1[maxn];
char s2[maxn];
int dp[2][maxn];
int main()
{
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
while(scanf("%s%s",s1,s2)==2)
{
int n=strlen(s1);
int m=strlen(s2);
memset(dp,0,sizeof(dp));
int w=1;
for(int i=1;i<=n;i++ )
{
for(int j=1;j<=m;j++)
{
if(s1[i-1]==s2[j-1])
{
dp[w][j]=dp[w^1][j-1]+1;
}
else
{
dp[w][j]=max(dp[w^1][j],dp[w][j-1]);
}
}
w^=1;
}
w^=1;
printf("%d\n",dp[w][m]);
}
}
题目：对给定字符串，进行插入或删除操作最少的次数，使得新的字符串为回文格式。
思路：假设给定字符串为str，str长度为len，str的逆序字符串为rev，则最少的次数为len-LCS( str ,rev );
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 1005
int main()
{
char str[maxn],rev[maxn];
int n,i,j,w,arr[2][maxn];
while(scanf("%d",&n)!=EOF,n)
{
scanf("%s",str);
for(i=n-1,j=0;j<n;j++,i--)
{
rev[j]=str[i];
}
w=1;
memset(arr,0,sizeof(arr));
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(str[i-1]==rev[j-1]) arr[w][j]=arr[w^1][j-1]+1;
else arr[w][j]=max(arr[w][j-1],arr[w^1][j]);
}
w^=1;
}
w^=1;
printf("%d\n",n-arr[w][n]);
}
}
