Make Palindrome UVA - 10453

题意：添加尽量少的字符使得s串成为回文串，并输出这样得解。

题解：dp[ i ][ j ]表示i~j串需要添加的最少字符。

当s[ i ]==s[ j ]时，dp[ i ][ j ]=dp[ i +1 ][ j - 1 ];

当s[ i ]! =s[ j ]时，dp[ i ][ j ]=min( dp[ i ][ j ]，min(dp[ i+1 ][ j ],dp[ i ][ j - 1 ]+1);

头疼的是打印解。

（1）顺着刷

void solve(){
    for(int i=0;i<n;i++) { dp[i+1][i]=0; dp[i][i]=0; } 
    
    for(int len=1;len<n;len++){
        for(int i=0;i+len<n;i++){
            dp[i][j]=INF;
            int j=i+len;
            if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];
            else dp[i][j]=min(dp[i][j],min(dp[i+1][j],dp[i][j-1])+1);
        }
    }
    cout<<dp[0][n-1]<<" ";
}

（2）逆着刷

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=1005;

int n;
int dp[maxn][maxn],rec[maxn][maxn];
char s[maxn];

void solve(){
    memset(dp,0,sizeof(dp));
    memset(rec,0,sizeof(rec));
    
    for(int i=n-1;i>=0;i--){
        for(int j=i+1;j<n;j++){
            if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];
            else{
                if(dp[i+1][j]>dp[i][j-1]){
                    dp[i][j]=dp[i][j-1]+1;
                    rec[i][j]=1;
                }
                else{
                    dp[i][j]=dp[i+1][j]+1;
                    rec[i][j]=-1;
                }
            }
        }
    }
    cout<<dp[0][n-1]<<" ";
}

void print(int i,int j){
    if(i>j) return ;
    if(i==j) printf("%c",s[i]);
    else if(rec[i][j]==0){
        printf("%c",s[i]);
        print(i+1,j-1);
        printf("%c",s[i]);
    }
    else if(rec[i][j]==1){
        printf("%c",s[j]);
        print(i,j-1);
        printf("%c",s[j]);
        
    }
    else{
        printf("%c",s[i]);
        print(i+1,j);
        printf("%c",s[i]);
    }
}


int main()
{   while(scanf("%s",s)!=EOF){
        n=strlen(s);
        
        solve();
        print(0,n-1);
        cout<<endl;
    }
    return 0;
}