Uva(1437)(String painter)

链接：https://vjudge.net/problem/UVA-1437
思路：想了半天也没啥思路，总感觉贪心能错其实不太行，后来知道这是个区间dp的题，虽然对区间dp没太多了解，但是先把本题记录在这里回去慢慢理解吧。首先是对b串进行遍历，先假设总共刷b的长度那么多次，如果中间有两块相等（不管有没有间隔），总的刷次数就可以-1，这样先对b进行预处理，然后我们比对a和b，如果对应位置不等，那么就像等于从空的开始刷成b，就跟预处理所得到的需要的次数一样，如果相等，该位置就可以忽略，那么只用看前后两个子串需要的次数即可，这就是所谓的区间dp（做法是理解了，但是区间dp还是不太理解，慢慢领悟吧）
代码：

#include<bits/stdc++.h>
using namespace std;
string a,b;
const int maxn = 110;
int dp[maxn][maxn];
int ans[maxn];

int main(){
    while(cin>>a>>b){
        memset(dp,0,sizeof(dp));
        memset(ans,0,sizeof(ans));
//预处理b串
        for(int j=0;j<a.size();j++){
            for(int i=j;i>=0;i--){
                dp[i][j] = dp[i+1][j]+1;
                for(int k=i+1;k<=j;k++){
                    if(b[i]==b[k])
                    dp[i][j] = min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
                }
            }
        }
        for(int i=0;i<a.size();i++)
            ans[i] = dp[0][i];
            for(int i=0;i<a.size();i++){
                if(a[i]!=b[i])//不等则为预处理的结果
                for(int j=0;j<i;j++)
                ans[i] = min(ans[i],ans[j] + dp[j+1][i]);
                else ans[i] = ans[i-1];//相等则等于前一个子问题
            }
        cout<<ans[a.size()-1]<<endl;
    }
    return 0;
}