样例

#include<iostream>
#include<vector>
using namespace std;

const int INF = 1e9;
string s;

int main(){
    cin >> s;
    int n = s.size();
    vector<vector<int>> f(n, vector<int>(n, INF));

    for(int i = 0; i < n; i ++ )f[i][i] = 0;
    for(int len = 2; len <= n; len ++ ){
        for(int i = 0; i + len - 1 < n; i ++ ){
            int r = i + len - 1;
            if(s[i] == s[r]){
                if(len == 2)
                    f[i][r] = 0;
                else
                    f[i][r] = f[i + 1][r - 1];
            }
            else f[i][r] = min(f[i + 1][r], f[i][r - 1]) + 1;
        }
    }
    cout << f[0][n - 1] << endl;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla