题目大意：
给你两个串，有一个操作！ 操作时可以把某个区间（L,R） 之间的所有字符变成同一个字符。现在给你两个串A,B要求最少的步骤把A串变成B串。
题目分析：
区间DP， 假如我们直接想把A变成B，那么我们DP区间的时候容易产生一个问题：假如我这个区间更新了，那么之前这个区间的子区间内DP出来的值就没用。
然后考虑到这里一直想不过去。最后看了看题解才知道.
我们可以先预处理一下怎么将一个空串变成B串需要的操作数。
这样我们就不用考虑子区间被覆盖的情况了。
如区间L,R
我们需要考虑的是点L是否需要单独刷一次。
如果需要单独刷一次那么就是：dp[L][R] = dp[L+1][R] + 1;
如果不需要单独刷，那么就是从一个点k刷到点L的时候顺便把L给刷掉。
那么我们就不用再占用刷的次数了。
故：if(b[L] == b[k]) dp[L][R] = min(dp[L][R], dp[L+1][k] + dp[k+1][R]);
因此我们dp[L][R] 保存的就是最小刷的次数了。
然后下面我们把答案枚举一下就行了。
============================================================================================
记忆化搜索
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL INF = 0xfffffff;
const LL maxn = ;
int dp[maxn][maxn], ans[maxn];
char a[maxn], b[maxn];
int DFS(int L,int R)
{
if(dp[L][R])
return dp[L][R];
if(L == R)
return dp[L][R] = ;
if(L > R)
return ;
dp[L][R] = DFS(L+,R) + ;
for(int k=L+; k<=R; k++)
{
if(b[L] == b[k])
dp[L][R] = min(dp[L][R], DFS(L+,k) + DFS(k+,R) );
}
return dp[L][R];
} int main()
{ while(cin >> a >> b)
{
memset(dp, , sizeof(dp));
int n = strlen(a);
for(int i=; i<n; i++)
DFS(, i); for(int i=; i <n; i++)
{
ans[i] = dp[][i];
if(a[i] == b[i])
ans[i] =i?ans[i-]:; for(int j=; j<i; j++)
ans[i] = min(ans[i], ans[j]+dp[j+][i]);
}
printf("%d\n", ans[n-]);
}
return ;
}
=========================================================================
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL INF = 0xfffffff;
const LL maxn = ;
int dp[maxn][maxn], ans[maxn];
char a[maxn], b[maxn]; int main()
{ while(cin >> a >> b)
{
memset(dp, , sizeof(dp));
int n = strlen(a); for(int len=; len<n; len++)
{
for(int i=; 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]);
}
}
}
} for(int i=; i <n; i++)
{
ans[i] = dp[][i];
if(a[i] == b[i])
ans[i] =i?ans[i-]:; for(int j=; j<i; j++)
ans[i] = min(ans[i], ans[j]+dp[j+][i]);
}
printf("%d\n", ans[n-]);
}
return ;
}