题目链接：?pid=2476
一：题意：
给定你两个字符串str1与str2，str1为初始串，str2是目标串。要你将str1变成str2串，
你能做的操作只有：在str1中选取一段连续的区间将其变成全都变成同一个字母（任意一个小写字母）。
问你str1最少要经过多少次这样的操作能变成str2.
二，解析：
我先计算如果将一个空白串变成str2需要的最小步数。
dp[j][i] 表示将区间[j,i]空白串变成str2最少步数。递推方程：
if(str2[j]==str2[k])
dp[i][j]=min(dp[i][j]，dp[j+1][k]+dp[k+1][i])。
sun[i]表示将区间[0,i] str1 变成str2最小步数。sun数组是用dp来初始化的sun[i]=dp[0][i]。
这里要注意两点：
(1)，对于dp[i][j]，，区间[i，j]，的j节点一定会被染色。这样是递推方程的来源。
(2)，对于递推行的dp要注意只要已经计算过所记录过的一定是最优的，我们要做的就是用已有的
最优推出当前要计算过的最优值。
三，代码：
#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>using namespace std;char str1[150],str2[150];int dp[150][150];//dp[i][j]空白串变成目标串在区间[i,j]的变化最少步数(最优)//注意：每一个区间[x,y]最后一个节点一定会被染色所以dp[i][i]==1;int sun[150];//sun[i]记录在区间[0,i]上将str1变成str2最小步数int main(){while(scanf("%s%s",str1,str2)!=EOF){int len=strlen(str2);//空白串染色成str2memset(dp,0,sizeof(dp));for(int i=0;i<len;i++){for(int j=i;j>=0;j–){//区间[j,i]dp[j][i]=dp[j+1][i]+1;//j节点单独染色for(int k=j+1;k<=i;k++){//区间中插入kif(str2[k]==str2[j])//两个可以一起刷{dp[j][i]=min(dp[j][i],dp[j+1][k]+dp[k+1][i]);//dp[j+1][k] 表示k节点一定单独染色}}}}for(int i=0;i<len;i++)sun[i]=dp[0][i];for(int i=0;i<len;i++){if(str1[i]==str2[i])sun[i]=sun[i-1];else{//用两个最优来计算sun[i]最优for(int j=0;j<i;j++)sun[i]=min(sun[i],sun[j]+dp[j+1][i]);}}printf("%d\n",sun[len-1]);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
走过一段路，风景毕竟不相同。这段惠风和畅，
