String painter
题目大意：给你2个字符串，字符串s1和目标串s2。每次能选择一个区间进行粉刷（这个区间所有字符变成同一任一字符），问最少需要多少次将字符串s1变成目标串s2。
解题思路：由复杂到简单，先求一个空白字符串变成目标串需要的次数，用dp[i][j]表示空白串从i到j粉刷需要最小的次数。然后再比较s1与s2。
代码：
#include <bits/stdc++.h> using namespace std; char s1[110],s2[110]; int ans[110]; int dp[110][110]; int main() { while(~scanf("%s%s",s1,s2)){ int n=strlen(s2); memset(dp,0,sizeof(dp)); memset(ans,0,sizeof(ans)); for(int i=0;i<n;i++)dp[i][i]=1; for(int i=0;i<n;i++){ for(int j=i;j>=0;j--){ dp[j][i]=dp[j+1][i]+1; for(int k=j+1;k<=i;k++){ if(s2[j]==s2[k])dp[j][i]=min(dp[j][i],dp[j+1][k]+dp[k+1][i]); } } } for(int i=0;i<n;i++)ans[i]=dp[0][i]; for(int i=0;i<n;i++){ if(s1[i]==s2[i]){ if(i==0)ans[i]=0; else ans[i]=ans[i-1]; }else{ for(int k=0;k<i;k++){ ans[i]=min(ans[i],ans[k]+dp[k+1][i]); } } } printf("%d\n",ans[n-1]); } return 0; }