题目描述
blablabla
样例
include[HTML_REMOVED]
using namespace std;
string s;
int dp[1010][1010];
int main()
{
cin>>s;
int len=s.length();
s=’ ‘+s;
memset(dp,0,sizeof dp);
for(int i=1;i<=len;i)
dp[i][i]=1;
for(int i=1;i<=len;i)
for(int j=1;j<i;j)
dp[i][j]=0;
for(int i=2;i<=len;i)
{
for(int l=1;l+i-1<=len;l++)
{
int r=l+i-1;
if(s[l]==s[r]) dp[l][r]=max(dp[l+1][r],max(dp[l][r-1],max(dp[l+1][r-1]+2,dp[l][r])));
else dp[l][r]=max(dp[l+1][r],max(dp[l][r-1],max(dp[l+1][r-1],dp[l][r])));
}
}
cout<<len-dp[1][len];
return 0;
}