题目描述
blablabla
两种dp方式,不是很难
样例
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010;
string s;
int f[N][N];
signed main()
{
cin>>s;
int n=s.size();
f[0][0]=1;
for(int l=n-1;l>=0;l--)
{
for(int r=l;r<n;r++)
{
if(l==r)
{
f[l][r]=1;
continue;
}
if(s[l]==s[r])
{
f[l][r]=f[l+1][r-1]+2;
}
f[l][r]=max(max(f[l][r-1],f[l][r]),f[l+1][r]);
}
}
cout<<n-f[0][n-1]<<'\n';
return 0;
}
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010;
int dp[N][N];
string str_1;
char str_2[N];
signed main()
{
cin>>str_1;
int n=str_1.size();
for(int i=0;i<n;i++)
{
str_2[i]=str_1[n-i-1];
}
for(int i=0;i<n;i++)
{
if(str_1[0]==str_2[i])
{
for(int j=i;j<n;j++)
{
dp[0][j]=1;
}
break;
}
}
for(int i=0;i<n;i++)
{
if(str_1[i]==str_2[0])
{
for(int j=i;j<n;j++)
{
dp[i][0]=1;
}
break;
}
}
for(int i=1;i<n;i++)
{
for(int j=1;j<n;j++)
{
if(str_1[i]==str_2[j])
{
dp[i][j]=dp[i-1][j-1]+1;
}
dp[i][j]=max(max(dp[i][j],dp[i][j-1]),dp[i-1][j]);
}
}
cout<<n-dp[n-1][n-1]<<'\n';
return 0;
}