用dp[i][j]表示把[i,j]的字符串str改写成回文串需要的最小操作步数。
并且假设所有dp[ii][jj] (ii>i , jj<j)都为已知，即包括dp[i+1][j]、dp[i][j-1]、dp[i+1][j-1]这三者都已知，则：
1、
如果str[i]==str[j]，那么dp[i][j]=dp[i+1][j-1]；
2、
否则dp[i][j]可以分为：
①“一个字符”+“一个回文串”型：那么我们可以在str[i,j]后面加上一个字符，或者删去第一个字符来使得其变成回文串，这种情况即dp[i+1][j]+1；
②“一个回文串”+“一个字符”型：那么我们可以在str[i,j]前面加上一个字符，或者删去最后一个字符来使得其变成回文串，这种情况即dp[i][j-1]+1；
③“一个字符”+“一个回文串”+“另一个字符”型：那么我们就修改第一个或者修改最后一个字符，这种情况即dp[i+1][j-1]+1；
这三种情况中，选择最小的那个，就是dp[i][j]的值。
故不难得到：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[][];
char str[];
int main()
{
scanf("%s",str+);
int len=strlen(str+);
memset(dp,,sizeof(dp));
for(int k=;k<=len;k++)
{
for(int i=,j=i+k-;j<=len;i++,j++)
{
if(str[i]==str[j]) dp[i][j]=dp[i+][j-];
else dp[i][j]=min( min(dp[i+][j]+,dp[i][j-]+),dp[i+][j-]+ );
}
}
printf("%d\n",dp[][len]);
}