题解 P1435 【回文字串】

张佳 · 2017-06-21 11:50:01 · 题解

设计状态f[i][j]表示让前i个字符和后j个字符构成回文串，最少要添加几个字符，则初始化

f[i][0]=i

f[0][i]=i

易得转移方程f[i][j]= f[i-1][j-1] (a[i]==a[n-j+1])

                          min{f[i-1][j],

f[i][j-1])+1

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[1002];
int f[1002][1002], n;
int min(int x, int y) { return x>y?y:x; }
int main() {
    scanf("%s", a+1);
    n=strlen(a+1);
    for(int i=1; i<=n; i++) {
        f[i][0]=i;
        f[0][i]=i;
    }
    for (int i=1; i<=n; i++)
        for (int j=1; i+j<=n; j++) {
            if (a[i]==a[n-j+1]) 
                f[i][j]=f[i-1][j-1];
            else {
                f[i][j]=min(f[i-1][j], f[i][j-1])+1;
            }
        }
    int ans=100000000;
    for (int i=0; i<=n; i++) {//调试观察用 
        for (int j=0; j<=n; j++)
            cout<<f[i][j]<<" ";
        cout<<endl;
    }
    for (int i=0; i<n; i++) {
        ans=min(min(f[i][n-i], ans), f[i][n-1-i]);
    }
    cout<<ans;
    return 0;
}