题目链接：

　　

题目描述：

　　给出两个长度相同的字符串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 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           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