题目描述
blablabla
直接上代码,就是求最少落叶
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N];
int dp[N][N];
string s;
int main()
{
cin>>s;
int n=s.size();
for(int i=1;i<=s.size();i++)
a[i]=s[i-1];
memset(dp,0x3f,sizeof dp);
for(int len=1;len<=n;len++)
{
for(int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
if(len==1) dp[i][j]=0;
if(len==2)
{
if(a[i]==a[j]) dp[i][j]=0;
else dp[i][j]=2;
}
else {
if(a[i]==a[j]) dp[i][j]=min(dp[i+1][j-1],dp[i][j]);
else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
}
}
}
cout<<dp[1][n]<<endl;
return 0;
}