String painter 区间dp

题意：给你两个串a和b，每次可以将就a的一个区间改成一种字母，区间长可以为1，求改多少次可以将a变成b。

思路：考虑将空白串变为b串的最小次数，再考虑a能否减少次数，令ans[ i ]为 a[1]~a[ i ]改为b[1]~b[ i ]的最小次数，如果啊a[ i ]==b[ i ]，ans[ i ]=ans [i-1],若不等，则ans[ i ]=min(ans[i] , ans[ j ] +dp[ j+1 ][i] ),意思是1到j区间的ans已知，把j+1到i区间当成空串，dp[ j+1 ][i]就是由空串变为b串的最小次数。

AC代码：

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 char a[150],b[150];
 5 int dp[150][150];
 6 int ans[200];
 7 int main()
 8 {
 9     while(cin>>a+1>>b+1){
10         int n=strlen(b+1);
11         for(int i=n;i>=1;i--){
12             for(int j=i;j<=n;j++){
13                 dp[i][j]=dp[i+1][j]+1;
14                 for(int k=i+1;k<=j;k++){
15                     if(b[i]==b[k])
16                         dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]);
17                 }
18             }
19         }
20         for(int i=1;i<=n;i++){
21             if(a[i]==b[i]){
22                 if(i==0)
23                     ans[i]=0;
24                 else
25                     ans[i]=ans[i-1];
26                 continue;
27             }
28             ans[i]=dp[1][i];
29             for(int j=1;j<i;j++){
30                 ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
31             }
32         }
33         cout<<ans[n]<<'
';
34     }
35 }