解题思路:
注意事项:
参考代码:
#include
#include
int max(int x,int y)//比较返回最大的那个
{
if(x>y)
return x;
else
return y;
}
int main()
{
int dp[1000][1000];
char arr[1000];
scanf("%s",arr);
int n=strlen(arr);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(arr[i]==arr[n-j-1])//当字符相同时,此处等于上一步加一(具体了解动态规划)
dp[i+1][j+1]=dp[i][j]+1;//保存的是原串的i号位置之前的所有字符跟逆序串的j号位置之前的所有字符的最大公共子序列
else
{
dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);//如果不相同,等于较大的,dp[i+1][j+1]不会比其中任何一个小,也不会比较大的大
}
}
printf("%d",n-dp[n][n]);
return 0;
}
0.0分
2 人评分