题意：就是给定两个字符串，第一个是初始串，第二个是目标串，问你把初始串变到目标串最少需要多少串！
分析：此题分两步，第一步是假设开始的初始串是空串，然后就进行区间dp，dp[i][j]代表把区间[i,j]变到与目标串相同的时候最少需要的步数，所以可以初始化dp[i][j]=dp[i+1][j]+1;
然后如果str2[i]==str2[k]就可以有dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j])。具体看代码实现吧！
代码实现：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; int dp[][],res[];
char str1[],str2[]; int min(int x,int y)
{
return x<y?x:y;
} int main()
{
int i,j,k,len;
while(scanf("%s%s",str1,str2)!=EOF)
{
len=strlen(str1);
memset(dp,,sizeof(dp));
for(j=;j<=len;j++)
{
for(i=;i<len-j+;i++)
{
dp[i][i+j-]=dp[i+][i+j-]+;
for(k=i+;k<=i+j-;k++)
{
if(str2[i]==str2[k])
dp[i][i+j-]=min(dp[i][i+j-],dp[i+][k]+dp[k+][i+j-]);
}
}
} for(i=;i<len;i++)
res[i]=dp[][i]; for(i=;i<len;i++)
{
if(str1[i]==str2[i])
{
if(i==)
res[i]=;
else
res[i]=res[i-];
}
else
{
for(j=;j<i;j++)
res[i]=min(res[i],res[j]+dp[j+][i]);
}
} printf("%d\n",res[len-]);
}
return ;
}