题意：给出两个串a和b，一次只能将一个区间刷一次，问最少几次能让a=b
思路:首先考虑最坏的情况，就是先将一个空白字符串刷成b需要的次数，直接区间DP[i][j]表示i到j的最小次数。
再考虑把a变成b的次数 ans[i]：a从（0，i）变成b（0，i）所需的最小次数
初始化ans[i]=dp[0][i]
如果a[i]==b[i],则ans[i]=ans[i-1];
由小区间更新到大区间
//#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
// #include<malloc.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define LL long long
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
// const double pi = acos(-1);
const LL MOD = ;
const int N = ; // inline int r(){
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
// return x*f;
// }
char a[N],b[N];
int dp[N][N];
int ans[N]; int main(){
while(~scanf("%s%s",a,b)){
int n=strlen(a);
clc(dp,);
for(int i=;i<n;i++){
for(int j=i;j<n;j++){
dp[i][j]=j-i+;
}
} for(int len=;len<n;len++){
for(int i=;i<n&&i+len<n;i++){
int j=i+len;
dp[i][j]=dp[i+][j]+;
for(int k=i+;k<=j;k++){
if(b[i]==b[k])
dp[i][j]=min(dp[i][j],dp[i+][k]+dp[k+][j]);
}
}
} if(a[]==b[]) {
ans[]=;
}
else
ans[]=;
for(int i=;i<n;i++){
ans[i]=dp[][i];
if(a[i]==b[i]){
ans[i]=ans[i-];
}
else{
for(int k=;k<i;k++){
ans[i]=min(ans[i],ans[k]+dp[k+][i]);
}
}
}
printf("%d\n",ans[n-]);
}
return ;
}