题意：有一个原始串，和一个目标串（都由小写字母组成），有一个操作，可以将字符串的一段子串变成一样的字母，问最少的操作数使得原始串变成目标串
分析：可以分两个步骤来解题
1：计算由空串变为目标串的最最少操作数
2：然后利用1步骤得到的答案去计算由原始串得到目标串的最少操作数
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cstdlib> #include<cmath> #include<cstdlib> #include<vector> #include<queue> using namespace std; typedef long long LL; const int maxn=105; int dp[maxn][maxn]; char s[maxn],t[maxn]; int ans[maxn]; int main() { while(~scanf("%s%s",s+1,t+1)) { int len=strlen(s+1); memset(dp,0,sizeof(dp)); for(int i=1;i<=len;++i) dp[i][i]=1;//初始化 for(int l=1;l<len;++l) { for(int i=1;i+l<=len;++i) { int j=i+l; dp[i][j]=dp[i+1][j]+1;//单独涂第i个位置 for(int k=i+1;k<=j;++k)//考虑到中间有相同的字符，一起涂的时候更优进行更新 if(t[i]==t[k]) dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]); } } for(int i=1;i<=len;++i) ans[i]=dp[1][i];//ans数组记录答案 ans[0]=0; for(int i=1;i<=len;++i) { if(s[i]==t[i])ans[i]=ans[i-1];//对应位置相等，不用涂 else for(int j=1;j<i;++j)//不相等，分解区间，求最优值，枚举区间相当于由空转化为目标串的长度 ans[i]=min(ans[i],ans[j]+dp[j+1][i]); } printf("%d\n",ans[len]); } return 0; }
原文：http://www.cnblogs.com/shuguangzw/p/5075396.html
