题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

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

const int N = 1010;
char s[N];
int n;
/*
f[i][j] 表示i-j的最大回文字符串长度

if(len == 1) f[i][j] = 1;
else {
    if(s[i] == s[j]) f[i][j] = f[i+1][j-1] + 2 // 上一个状态 + 2有两个字符
    else f[i][j] = max(f[i][j-1] , f[i+1][j]); // f[i][j-1] 表示i在回文串 j不在
                                               // f[i + 1][j] 表示i不在 j在
}
*/
int main(){
    scanf("%s" , s);
    n = strlen(s);
    vector<vector<int>> f(n + 1,vector<int>(n + 1));

    /*
    区间dp
    枚举顺序：len=1 00,11,22,33,44
              len=2 01,12,23,34
              len=3 02,13,24
              len=4 03,14
    */
    for(int len = 1 ; len <= n ; len++){ // 区间dp模板 先枚举长度
        for(int i = 1 ; i + len - 1 <= n; i++){ // 再枚举左端点，左端点不超过右端点
            int j = i + len - 1; // 右端点
            if(len == 1) f[i][j] = 1;
            else{
                if(s[i - 1] == s[j - 1]) 
                    f[i][j] = max(f[i][j] , f[i + 1][j - 1] + 2); // 上一个状态 + 2有两个字符
                else 
                    f[i][j] = max(f[i + 1][j] , f[i][j - 1]);// f[i][j-1] 表示i在回文串 j不在
            }
        }
    }
    cout <<n - f[1][n] << endl;
    return 0;
}