http://www.51nod.com/Challenge/Problem.html#problemId=1092
解决本题的关键是发现插入一个字符相当于删除一个字符
思路一：区间dp
dp[i][j]表示s[i…j]最少删除几个字符，使s[i…j]构成回文串
由小区间向大区间扩大计算
如果s[i]=s[j]，那么不用删除任何字符，在s[i+1…j-1]的基础上，s[i…j]是回文串，所以dp[i][j]=dp[i+1][j-1]
如果s[i]!=s[j]，那么就要删除s[i]或者s[j]，构成回文串s[i+1…j]或s[i…j-1]，所以dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1
#include<cstdio> #include<cstring> #include<algorithm> #define N 1001 using namespace std; int dp[N][N]; char s[N]; int main() { scanf("%s",s+1); int n=strlen(s+1); for(int i=n-1;i;--i) for(int j=i+1;j<=n;++j) { if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]; else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1; } printf("%d",dp[1][n]); }
思路二：与反串求最长公共子序列
一个字符想要不被删除，就必须在后面找到一个与之回文匹配的字符
原串和反串对应位置的字符相同，该字符就可以留下
#include<cstdio> #include<cstring> #include<algorithm> #define N 1001 using namespace std; int dp[N][N]; char s[N],t[N]; int main() { scanf("%s",s+1); int n=strlen(s+1); for(int i=1;i<=n;++i) t[i]=s[n-i+1]; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(s[i]!=t[j]) dp[i][j]=max(dp[i-1][j],dp[i][j-1]); else dp[i][j]=dp[i-1][j-1]+1; printf("%d",n-dp[n][n]); }
原文：https://www.cnblogs.com/TheRoadToTheGold/p/14659822.html