题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2395
题目大意：给定两个长度相等，只有小写字母组成的字符串s和t，每步可以把s的一个连续字串“刷“成同一个字母，问至少需要多少步才能把s变成t。比如：s = bbbbbbb, t = aaabccb，最少需要两步可实现将s变成t：bbbbbbb --> aaabbbb --> aaabccb。（字符串长度不超过100）
题解：由于题目历史较为久远，网上鲜有关于此题的题解。以下内容仅个人YY之作，难登大雅之堂。
初见此题有DP的即视感，由于”刷“这个操作随意性强，没有左右的顺序，因此排除一般的线性DP，考虑区间DP。
我认为DP难度在于选择状态，而状态的选取通常与题目的特殊性质紧密相连。而构造状态的技巧在于，考虑怎样的大状态能由小状态更新过来，更新方法与题目性质挂钩。
首先预处理出p[l][r][ch]对于s1（终状态）区间[l,r]上底色为ch的情况下，最少需要几步操作变为s1上的对应状态。
p[l][r][ch] = p[l + 1][r - 1][ch]（s1[l] == ch）
p[l][r][ch] = min{p[l][k][s1[l]] + p[k + 1][j][ch] + 1} （s1[l] != ch）
f[l][r]表示从l到r这段区间，由s2变为s1需要多少步操作。与题目中”刷”的操作挂钩，考虑从l开始刷k个格子全部变为s1[l]，这样[l,k]上已经涂满了底色s1[l]，后续操作数由p[l][k][s1[l]]转移。
f[l][r] = f[l + 1][r]（s1[l] == s2[l]）
f[l][r] = min{p[l][r][s1[l]] + f[k + 1][r] + 1} （s1[l] != s2[l]）
时间复杂度O(len*len*len*26)，以为会T，没想到跑得还挺快的…
1 //By Ro_mantic 2015-11-04 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <ctime> 6 #include <cmath> 7 #include <cctype> 8 #include <climits> 9 #include <string> 10 #include <algorithm> 11 using namespace std; 12 13 const int MaxN = 100; 14 char s1[MaxN + 5], s2[MaxN + 5]; 15 int len, len1, len2, Minn, p[MaxN + 5][MaxN + 5][MaxN], 16 f[MaxN + 5][MaxN + 5]; 17 18 void Prepare() 19 { 20 len1 = strlen(s1); 21 for (int i = 0; i <= len1 - 1; i++) 22 for (int j = 'a'; j <= 'z'; j++) 23 if (s1[i] == j) p[i][i][j] = 0; 24 else p[i][i][j] = 1; 25 for (int len = 2; len <= len1; len++) 26 for (int l = 0; l <= len1 - len; l++) 27 for (int ch = 'a'; ch <= 'z'; ch++) 28 { 29 int r = l + len - 1; 30 if (s1[l] == ch) p[l][r][ch] = p[l + 1][r][ch]; 31 else 32 { 33 Minn = p[l + 1][r][ch] + 1; 34 for (int k = l + 1; k <= r; k++) 35 Minn = min(p[l + 1][k][s1[l]] + p[k + 1][r][ch] + 1, Minn); 36 p[l][r][ch] = Minn; 37 } 38 } 39 //printf("%d\n", p[0][8]['a']); 40 } 41 42 void Solve() 43 { 44 len1 = strlen(s1); 45 for (int i = 0; i <= len1 - 1; i++) 46 if (s1[i] == s2[i]) f[i][i] = 0; else f[i][i] = 1; 47 for (int len = 2; len <= len1; len++) 48 for (int l = 0; l <= len1 - len; l++) 49 { 50 int r = l + len - 1; 51 if (s1[l] == s2[l]) f[l][r] = f[l + 1][r]; 52 else 53 { 54 Minn = f[l + 1][r] + 1; 55 for (int k = l + 1; k <= r; k++) 56 Minn = min(p[l + 1][k][s1[l]] + f[k + 1][r] + 1, Minn); 57 f[l][r] = Minn; 58 } 59 } 60 printf("%d\n", f[0][len1 - 1]); 61 } 62 63 int main() 64 { 65 while (~scanf("%s", s2)) 66 { 67 scanf("%s", s1); 68 Prepare(); 69 Solve(); 70 } 71 }