y总视频里说的另外一种方法
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010 ;
int f[N][N] ;
int main()
{
string a ;
cin >> a ;
string b = a ;
int n = a.size() ;
reverse(b.begin(),b.end());
a = " " + a ;
b = " " + b ;
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= n ; j ++)
{
f[i][j] = max(f[i-1][j],f[i][j-1]) ;
if(a[i] == b[j]) f[i][j] = max(f[i-1][j-1] + 1,f[i][j]) ;
}
cout << n - f[n][n] << endl ;
return 0;
}