点击打开链接
题意：
给你两个字符串，a,and b
问你a->b,最少需要几步。
每步的操作是这样的，可以选定区间[l,r]使其中的字符都变成某个字符。
题解：
首先处理字符串b。
由空串->b串可以由一个区间转化而来，
然后用一个ans数组记录空->b的前i项最小变化量，
最后比较a串，
如果a[i]==b[i]，那么ans[i]=ans[i-1];
否则，再遍历一遍前i区间的组合，确定ans[i]的最小值。
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=105; char a[maxn],b[maxn]; int ans[maxn]; int dp[maxn][maxn]; int main(){ while(~scanf("%s %s",a+1,b+1)){ memset(dp,0,sizeof(dp)); int la=strlen(a+1); for(int l=0;l<=la;++l){ for(int i=1;i+l<=la;++i){ int j=i+l; dp[i][j]=dp[i+1][j]+1; for(int k=i+1;k<=j;++k){ if(b[i]==b[k])dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]); } } } for(int i=1;i<=la;++i) ans[i]=dp[1][i]; for(int i=1;i<=la;++i){ if(a[i]==b[i]){ ans[i]=ans[i-1]; }else{ for(int k=1;k<i;++k){ ans[i]=min(ans[i],ans[k]+dp[k+1][i]); } } } printf("%d\n",ans[la]); } return 0; }
