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]);
    }
 }