区间DP(最长回文子序列长度)

如样例，对于每个密码来说

若整个串是回文串，则表示无脱落，否则有脱落，脱落多少个相当于去掉多少个字符，使得整个串是回文串，即可以求最长回文子序列的长度

$ 时间复杂度O(N^2)，空间复杂度O(N^2) $

参考文献

蓝桥杯辅导课

AC代码

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

const int N = 1e3 + 10;

int n;
string s;
int f[N][N];

int main(){
    //读入
    cin >> s;
    n = s.size();

    //区间dp
    for (int len = 1 ; len <= n ; len ++){
        for (int l = 0 ; l + len - 1 < n ; l ++){
            int r = l + len - 1;
            if (len == 1) f[l][r] = 1;//特判区间长度为1
            else {
                if (s[l] == s[r]) f[l][r] = f[l + 1][r - 1] + 2;
                f[l][r] = max(f[l][r], f[l][r - 1]);
                f[l][r] = max(f[l][r], f[l + 1][r]);
            }
        }
    }

    cout << n - f[0][n - 1];
    return 0;

}