原题链接https://www.luogu.com.cn/problem/P8638

动态规划————最长公共子序列

就是将字符串颠倒，比较，用二维dp来维护如果这个时候字符相等就是dp[i][j] = dp[i - 1][j - 1] + 1。如果不相等就是dp[i][j] = std::max(dp[i - 1][j],dp[i][j - 1])。

#include <iostream>
#include <bits/stdc++.h>

#define ll long long

const ll N = 1e3 + 199;
ll dp[N][N];

void solve(){
    std::string a;
    std::cin >> a;
    ll n = a.size();
    std::string b = a;
    b = ' ' + b;
    reverse(a.begin(),a.end());
    a = ' ' + a;
    std::memset(dp,0,sizeof dp);
    for(ll i = 1; i <= n; i ++){
        for(ll j = 1; j <= n; j ++){
            if(a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = std::max(dp[i - 1][j],dp[i][j - 1]);
        }
    }
    std::cout << n - dp[n][n] << "\n";
}

int main(){
    ll t = 1;
    while(t --)
    solve();
    return 0;
}