原题 说实话，dp类型的并不是很常做， 这个题解讲的挺不错的------传送门 我们可以先求出一段无变成s2所需要的最小次数dp[i][j]（将无变成s2的第i到第j个所需要的最小次数），这里的方法是从前向后进行枚举，假如遇到了一样的字符，比如ABCDAE，其中1和5相同，那么dp[1][6]=min(dp[1][6],dp[2][4]+dp[5][6])这样递归。
递归完无的dp，就可以进一步递归s1了，那就是平常的简单的普通递归，不过要注意，加入s1[i]=s2[i]的话，那么d[i]=d[i-1]，否则d[i]=min(d[i],d[k]+dp[k+1][i]));
#include<bits/stdc++.h> using namespace std; const int MX=110; const int inf=0x3f3f3f3f; char s1[MX],s2[MX]; int dp[MX][MX],d[MX]; int main() { freopen("input.txt","r",stdin); while( ~scanf("%s %s",s1+1,s2+1) ){ memset(dp,0,sizeof(dp)); memset(d,0,sizeof(d)); int n=strlen(s1+1); for( int i=1 ; i<=n ; i++ ) // 最坏的情况下的dp for( int j=i ; j<=n ; j++ ) dp[i][j]=j-i+1; for( int i=2 ; i<=n ; i++ ){ // 把dp弄成s2最少的次数 for( int j=1 ; j<i ; j++ ){ dp[j][i]=dp[j][i-1]+1; for( int k=j ; k<=i-1 ; k++ ) if( s2[k]==s2[i] ) // 只有相等时才可以这样求 dp[j][i]=min(dp[j][i],dp[k+1][i-1]+dp[j][k]); } } for( int i=1 ; i<=n ; i++ ){ d[i]=dp[1][i]; // 最坏情况下的d if( s1[i]==s2[i] ) d[i]=(i==0?0:d[i-1]); // 若s1[i]==s2[i]时，就时上一次d[i-1]的答案 else for( int j=1 ; j<i ; j++ ) // 若不相等则进行分区域一个一个枚举 d[i]=min(d[i],d[j]+dp[j+1][i]); } printf("%d\n",d[n]); } return 0; }