String painter
题目链接：
http://poj.org/problem?id=2476
题意：
给出两个相同长度的字符串（仅由小写字母组成）s1，s2，每次操作可以将s1的任意一段区间改变成一个相同的字母，求将s1改变成s2所需的最少操作次数。
题解：
设dp[i][j]是将s1的区间[i，j]部分改成s2相同部分的最少操作次数，终点状态为dp[1][t]( t 为长度)。
先求出一个和s2没有任何相同部分的字符串转化为s2所需的最少次数，再求s1转化为s2的最少次数即可。
代码
#include<stdio.h>
#include<string.h>
const int N=101;
int dp[N][N];
char s1[N],s2[N];
int mmin(int x,int y)
{
return x<y?x:y;
}
void solve()
{
int n,m,x;
memset(dp,0,sizeof(dp));
while(~scanf("%s%s",s1+1,s2+1))
{
s1[0]=s2[0]='?';
int t=strlen(s1)-1;
for(int len=0;len<t;++len)
for(int i=1;i+len<=t;++i)
{
int j=len+i;
dp[i][j]=dp[i][j-1]+1;
for(int k=i;k<j;++k)
{
if(s2[k]==s2[j])dp[i][j]=mmin(dp[i][j],dp[k+1][j-1]+dp[i][k]);//考虑到s2串为aaaaaaa的情况这里必须是+dp[i][k],而不能是+dp[i][k-1]+1,刷[i,k]的时候顺便刷到 j 就好了
dp[i][j]=mmin(dp[i][j],dp[i][k-1]+dp[k][j]);
}
}
for(int len=0;len<t;++len)
for(int i=1;i+len<=t;++i)
{
int j=len+i;
if(s1[j]==s2[j]&&s1[i]==s2[i])
{
dp[i][j]=mmin(dp[i][j],dp[i+1][j-1]);
}
else
{
for(int k=i;k<=j;++k)
if(dp[i][k]+dp[k+1][j]<dp[i][j])
dp[i][j]=dp[i][k]+dp[k+1][j];
}
}
printf("%d
",dp[1][t]);
}
}
int main()
{
solve();
return 0;
}