动态规划解决（类似最长公共子序列）

解题思路:

注意事项:

参考代码:

#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;

}