Description
There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can change a segment of characters of a string to any other character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What‘s the minimum number of operations?
Input
Input contains multiple cases. Each case consists of two lines:
The length of both strings will not be greater than 100.
Output
A single line contains one integer representing the answer.
Sample Input
zzzzzfzzzzz abcdefedcba abababababab cdcdcdcdcdcd
Sample Output
6 7
令dp[l][r] 为l到r区间从空串刷成b串所需的最少次数
则dp[l][r] = min(dp[l][k] + dp[k + 1][r])
如果 b[l] == b[r] dp[l][r] = min(dp[l][r], dp[l][r - 1])
最后设f[i]为1 到 i从a串刷到b串的最少次数(下标从1开始）
则 f[i] = min(f[j] + dp[j][i - 1])
如果a[i] == b[i]则 f[i] = min(f[i], f[i - 1])
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 8 using namespace std; 9 10 #define read() freopen("sw.in", "r", stdin) 11 12 const int MAX = 105; 13 char a[MAX], b[MAX]; 14 int dp[MAX][MAX]; 15 int f[MAX]; 16 17 void solve() { 18 int n = strlen(a); 19 for (int len = 1; len <= n; ++len) { 20 for (int l = 0; l + len - 1 < n; ++l) { 21 int r = l + len - 1; 22 dp[l][r] = len; 23 if (l == r) { 24 dp[l][r] = 1; 25 continue; 26 } 27 for (int k = l; k <= r; ++k) { 28 if (k + 1 > r) continue; 29 dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]); 30 } 31 if (b[l] == b[r]) dp[l][r] = min(dp[l][r - 1], dp[l][r]); 32 //printf("l = %d r = %d %d\n", l, r, dp[l][r]); 33 } 34 } 35 36 for (int i = 0; i < n; ++i) { 37 f[i + 1] = dp[0][i]; 38 if (a[i] == b[i]) f[i + 1] = min(f[i + 1], f[i]); 39 for (int j = 0; j < i; ++j) { 40 if (j + 1 > i) continue; 41 f[i + 1] = min(f[i + 1], f[j + 1] + dp[j + 1][i]); 42 } 43 } 44 45 //for (int i = 0; i < n; ++i) printf("%d ", f[i]); 46 printf("%d\n", f[n]); 47 48 49 } 50 51 int main() 52 { 53 54 int t; 55 //read(); 56 while (scanf("%s%s", a, b) != EOF) { 57 solve(); 58 } 59 //cout << "Hello world!" << endl; 60 return 0; 61 }
原文：http://www.cnblogs.com/hyxsolitude/p/3850819.html
