题目描述

blablabla

样例

blablabla

算法1

DP
阶段:串的长度len
状态：l-r中的最长回文子序列，即l,l+en-1 F[l][r]
决策:设字符串为s,若s[l]==s[r] f[l][r]=f[l-1][r-1]+2;
否则 f[l][r]=max(f[l+1][r],f[l][r-1]) 即：l与r不可能同时选，要么可能选l,要么可能选r,f[l][r]一定是[l+1][r],[l][r-1]中的最大值。

blablabla

时间复杂度

n^2

参考文献

C++ 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
string s;
int f[2000][2000];
int main(){
    cin>>s;
    for(int i=0;i<s.size();++i) f[i][i]=1;
    for(int len=2;len<=s.size();++len){
       for(int l=0;l+len<=s.size();++l){
           int r=l+len-1;
           if(s[l]==s[r]) f[l][r]=f[l+1][r-1]+2;
           else f[l][r]=max(f[l+1][r],f[l][r-1]);
       }
    }
    cout<<s.size()-f[0][s.size()-1];
}

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla