POJ

d.求对字符串最少添加几个字符可变为回文串。

s.

法1：直接对它和它的逆序串求最长公共子序列长度len。N-len即为所求。(N为串长度)

因为，要求最少添加几个字符，我们可以先从原串中找到一个最长回文子序列，然后对于原串中不属于这个回文子序列的字符，在串中的相应位置添加一个相同的字符即可。那么需要添加的字符数量即为N-len。

最长回文串可以看作是原串中前面和后面字符的一种匹配（每个后面的字符在前面找到一个符合位置要求的与它相同的字符）。这种的回文匹配和原串与逆序串的公共子序列是一一对应的（一个回文匹配对应一个公共子序列，反之亦然），而且两者所涉及到的原串中的字符数量是相等的，也就是最长公共子序列对应最长回文串。原因陈述完毕。

dp[i][j]表示原串前i个字符与逆序串前j个字符的最长公共子序列

if(str[i-1]==str2[j-1]){
　　dp[i][j]=dp[i-1][j-1]+1;
}
else{
　　dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}

法2：

dp[i][j]表示从i到j这段子串若变为回文串最少添加的字符数。

if(str[i]==str[j]){
　　dp[i][j]=dp[i+1][j-1];
}
else{
　　dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
}

c.法1

/*
用short险过

dp[i][j]表示原串前i个字符与逆序串前j个字符的最长公共子序列

if(str[i-1]==str2[j-1]){
    dp[i][j]=dp[i-1][j-1]+1;
}
else{
    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}

*/
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

#define MAXN 5005

short dp[MAXN][MAXN];
char str[MAXN],str2[MAXN];

int main(){

    int N;
    int i,j;

    while(~scanf("%d",&N)){

        scanf("%s",str);

        for(i=0,j=N-1;i<N;++i,--j){
            str2[i]=str[j];
        }

        memset(dp,0,sizeof(dp));
        for(i=1;i<=N;++i){
            for(j=1;j<=N;++j){
                if(str[i-1]==str2[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][N]);
    }

    return 0;
}

ps：其实可以用滚动数组

c'.滚动数组

/*
用short险过

dp[i][j]表示原串前i个字符与逆序串前j个字符的最长公共子序列

if(str[i-1]==str2[j-1]){
    dp[i][j]=dp[i-1][j-1]+1;
}
else{
    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}

*/
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

#define MAXN 5005

short dp[2][MAXN];//滚动数组
char str[MAXN],str2[MAXN];

int main(){

    int N;
    int i,j;

    while(~scanf("%d",&N)){

        scanf("%s",str);

        for(i=0,j=N-1;i<N;++i,--j){
            str2[i]=str[j];
        }

        memset(dp,0,sizeof(dp));
        for(i=1;i<=N;++i){
            for(j=1;j<=N;++j){
                if(str[i-1]==str2[j-1]){
                    dp[i%2][j]=dp[(i-1)%2][j-1]+1;
                }
                else{
                    dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]);
                }
            }
        }

        printf("%d
",N-dp[N%2][N]);
    }

    return 0;
}

c2.法2

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

#define MAXN 5005

short dp[MAXN][MAXN];
char str[MAXN];

int main(){

    int N;
    int i,j;

    while(~scanf("%d",&N)){
        scanf("%s",str);

        memset(dp,0,sizeof(dp));

        for(i=N-1;i>=0;--i){
            dp[i][i]=0;
            for(j=i+1;j<N;++j){
                if(str[i]==str[j]){
                    dp[i][j]=dp[i+1][j-1];
                }
                else{
                    dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
                }
            }
        }

        printf("%d
",dp[0][N-1]);
    }

    return 0;
}

c2'.滚动数组

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

#define MAXN 5005

short dp[2][MAXN];//滚动数组
char str[MAXN];

int main(){

    int N;
    int i,j;

    while(~scanf("%d",&N)){
        scanf("%s",str);

        memset(dp,0,sizeof(dp));

        for(i=N-1;i>=0;--i){
            dp[i%2][i%2]=0;
            for(j=i+1;j<N;++j){
                if(str[i]==str[j]){
                    dp[i%2][j]=dp[(i+1)%2][j-1];
                }
                else{
                    dp[i%2][j]=min(dp[(i+1)%2][j],dp[i%2][j-1])+1;
                }
            }
        }

        printf("%d
",dp[0][N-1]);
    }

    return 0;
}