题目链接：
题目描述：
给出两个长度相同的字符串a, b.对a可以进行区间更新(选择一个区间，把这个区间全部更新成相同的字符)，问要最少操作a多少次，a才能等于b？
解题思路：
区间DP真是神奇！人有多大胆，地有多大产！刚开始的时候就一直在想a和b怎么匹配，怎么状态转移求最小？想了一下午，wa了一下午········。
最后搜了一下题解发现是先处理一下b串，然后再对a串进行状态转移。对于串b，最要是看两个相同字符之间的区间了。我们可以预处理出来改变区间[x, y]里面的字符，操作的最小次数用dp[x, y]来存储。
预处理完了以后，我们就可以用dp来匹配a了。ans[i] 表示 a字符区间[0, i] 与 b字符区间[0, i]相同的最小操作数目。状态转移就是：ans[i] = min (dp[0, i], ans[j] + dp[j+1][i], ans[i-1](a[i] == b[i]))
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 typedef long long LL; 8 const int INF = 0x3f3f3f3f; 9 const int maxn = 110; 10 11 int dp[maxn][maxn], ans[maxn]; 12 char a[maxn], b[maxn]; 13 14 int main () 15 { 16 while (scanf ("%s %s", a, b) != EOF) 17 { 18 memset (dp, 0, sizeof(dp)); 19 int len = strlen (b); 20 for (int i=0; i<len; i++) 21 dp[i][i] = 1; 22 23 for (int i=1; i<len; i++) 24 for (int j=0; j+i<len; j++) 25 { 26 dp[j][j+i] = dp[j+1][j+i] + (b[j]==b[j+i]?0:1); 27 for (int k=j+1; k<j+i; k++) 28 if (b[k] == b[j]) 29 dp[j][j+i] = min (dp[j][j+i], dp[j+1][k]+dp[k+1][j+i]); 30 } 31 32 ans[0] = a[0]==b[0] ? 0:1; 33 for (int i=1; i<len; i++) 34 { 35 ans[i] = dp[0][i]; 36 if (a[i] == b[i]) 37 ans[i] = min (ans[i], ans[i-1]); 38 for (int j=0; j<i; j++) 39 ans[i] = min (ans[i], ans[j]+dp[j+1][i]); 40 } 41 42 printf ("%d\n", ans[len-1]); 43 } 44 return 0; 45 }
Hdu 2476 String painter (区间DP)
原文：http://www.cnblogs.com/alihenaixiao/p/4934027.html