密码脱落

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;
int n;
char a[N];
int dp[N][N];

int main ()
{
    cin >> a + 1;
    n = strlen(a + 1);
    for (int len = 1; len <= n; len ++)// 枚举区间长度
    {
        for (int l = 1; l + len - 1 <= n; l ++)// 枚举左端点
        {
            int r = l + len - 1; // 根据左端点的值可以直接求出右端点的值
            if (len == 1) dp[l][r] = 1; // 如果区间的长度为1，那么回文串的长度为1，即他自己本身
            else
            {
                dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
                if (a[l] == a[r])
                    dp[l][r] = max(dp[l][r], dp[l + 1][r - 1] + 2);
            }
        }
    }
    cout << n - dp[1][n] << endl;
    return 0;
}