算法1

区间dp， 分三种情况转移即可

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
#include<string>
using namespace std;

const int N = 1010;

int f[N][N];

int n;

string s;

int main()
{
    memset(f, 0x3f, sizeof f);
    cin >> s;
    int len = s.size();
    for(int i = 0; i < len; ++ i)
        f[i][i] = 0;
    for(int k = 2; k <= len; ++ k)
        for(int i = 0; i < len; ++ i)
                {
                    int j = i - k + 1;
                    if(j < 0) continue;
                    int &v = f[j][i];
                    int l = j, r = i;
                    while(s[l] == s[r]) -- r, ++ l;
                    if(l > r) v = 0;
                    else
                    {
                        v = min(v, f[l][r]);
                        v = min(v, f[j + 1][i] + 1);
                        v = min(v, f[j][i - 1] + 1);    
                    }
                }
    printf("%d", f[0][len - 1]);
    return 0;
}