给定2个长度相等的字符串a b

每次可以把a串的任意一段变成一样的字母。

问把a变成b最少需要几步。

思路：

1、dp[l][r] 表示把一个空字符串K 的[l,r] 变成 对应b[l,r]这段的最小花费。

那么 dp[l][r] 就是 把 K[l] -> b[l], 然后再把 K[l+1, r] -> b[l+1, r]

即： dp[l][r] = 1 + dp[l+1, r];

但是若存在b[l] =  b[i] ( l+1 <= i <= r)

那就可以先把空串 K[l, i] -> b[l], 然后再对 K[l+1, i] 操作。

所以若 b[l] == b[i] 则 dp[l, r] = dp[l+1, i] + dp[i+1, r];

若 b[l]!=b[i] ，那K[l] 变成b[l] 还是需要一步操作, : dp[l, r] = dp[l+1, i] + dp[i+1, r] +1;

2、ANS[i] 表示把a[1,i] -> b[1,i]的最小花费，简单dp，不再赘述

[cpp] view plaincopy

1. #include <cstdio>  
2. #include <iostream>  
3. #include <algorithm>  
4. #include <queue>  
5. #include <cstring>  
6. #include <cmath>  
7. using namespace std;  
8. const int inf = 1000000;  
9. const int N = 105;  
10. char s1[N], s2[N];  
11. int dp[N][N], len;//计算把空串的[i,j]段变成s2的[i,j]段需要的最少花费  
12. int dfs(int l, int r){  
13.     if(l > r)return 0;  
14.     if(dp[l][r] != -1) return dp[l][r];  
15.     if(l == r) return dp[l][l] = 1;  
16.     int ans = inf; //变第l个字符为 s2[l]  
17.     for(int i = l+1; i <= r; i++)  
18.     {  
19.         int tmp = dfs(l+1, i) + dfs(i+1, r);  
20.         if(s2[l] == s2[i])//变[l,i]字符为s2[l] ，这样单独变l 这步可以合并到变[l,i]这步里  
21.             ans = min(ans, tmp);  
22.         else  
23.             ans = min(ans, tmp+1);  
24.     }  
25.     return dp[l][r] = ans;  
26. }  
27. void cal_dp(){  
28.     memset(dp, -1, sizeof dp);  
29.     for(int i = 1; i <= len; i++)  
30.         for(int j = i; j <= len; j++)  
31.             dfs(i, j);  
32. }  
33.   
34. int ANS[N];//把s1前i位变成s2的最小花费  
35. void find_ans(){  
36.     ANS[1] = (s1[1] != s2[1]);  
37.     for(int i = 2; i <= len; i++)  
38.     {  
39.         ANS[i] = dp[1][i];//空串变成s2的花费  
40.         if(s1[i] == s2[i])  
41.             ANS[i] = ANS[i-1];  
42.         else  
43.         {  
44.             for(int j = 1; j < i; j++)  
45.                 ANS[i] = min(ANS[i], ANS[j]+dp[j+1][i]);  
46.         }  
47.     }  
48. }  
49. int main(){  
50.     while(~scanf("%s", s1+1)){  
51.         scanf("%s", s2+1);  
52.         len = strlen(s1+1);  
53.         cal_dp();  
54.         find_ans();  
55.         printf("%d\n", ANS[len]);  
56.     }  
57.     return 0;  
58. } 

HDU 2476