题意：
有a,b两字符串，现在你有一个刷子，每次可以任选一个区间，使这个区间变成你想要的字符，现在让你将a变成b，问最少刷多少次
题解：
考虑区间dp[i][j]，表示从第i到第j最少需要刷的次数。这里要先算从空串到b的dp，然后根据这个来推a串到b串的最小次数。
因为如果a的整个区间需要重新构造，这个区间就相当于空串。状态转移方程具体看代码
#include<cstdio>
#include<cstring>
#define F(i,a,b) for(int i=a;i<=b;i++) const int N=;
char a[N],b[N];
int dp[N][N],ans[N]; inline void up(int &a,int b){if(a>b)a=b;} int main()
{
while(~scanf("%s%s",a+,b+))
{
int n=strlen(a+);
memset(dp,,sizeof(dp));
F(i,,n)dp[i][i]=;
F(l,,n-)F(i,,n-l)
{
int j=i+l;
dp[i][j]=dp[i+][j]+;
F(k,i+,j)if(b[i]==b[k])up(dp[i][j],dp[i+][k]+dp[k+][j]);
}
F(i,,n)ans[i]=dp[][i];
F(i,,n)if(a[i]==b[i])ans[i]=(i==?:ans[i-]);
else F(j,,i-)up(ans[i],ans[j]+dp[j+][i]);
printf("%d\n",ans[n]);
}
return ;
}