String painter（区间dp，好题难题）

https://cn.vjudge.net/problem/HDU-2476

There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can change a segment of characters of a string to any other character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What’s the minimum number of operations?

Input

Input contains multiple cases. Each case consists of two lines: 
The first line contains string A. 
The second line contains string B. 
The length of both strings will not be greater than 100. 

Output

A single line contains one integer representing the answer.

Sample Input

zzzzzfzzzzz
abcdefedcba
abababababab
cdcdcdcdcdcd

Sample Output

6
7

直接将A转化成B不好办，我们可以先将一个空串转化成B，再比较与将A直接转化成B那个更快；

dp[i][j]代表空串变成B的[i,j]的最少操作

ans[i]表示A的[1, i]区间转换成B的[1, i]的最少操作

大佬学长的博客https://blog.csdn.net/Sirius_han/article/details/81323901

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
char a[105],b[105];
int dp[105][105];
int ans[105];
int dfs(int l,int r){
	if(dp[l][r]!=-1) return dp[l][r];
	if(l==r) return dp[l][r]=1;
	if(l>r) return 0;
	int ans=dfs(l,r-1)+1;
	for(int i=l;i<r;i++){
		if(b[i]==b[r])
		ans=min(ans,dfs(l,i-1)+dfs(i,r-1));
	}
	return dp[l][r]=ans;
}
int main(){
    while(~scanf("%s%s",a+1,b+1)){
    	int len=strlen(a+1);
		memset(dp,-1,sizeof(dp));
		for(int i=1;i<=len;i++){
			ans[i]=dfs(1,i);
			if(a[i]==b[i]) ans[i]=ans[i-1];
			for(int j=1;j<i;j++){
				ans[i]=min(ans[i],ans[j]+dfs(j+1,i));
			}
		}
		printf("%d\n",ans[len]); 
	}
	return 0;
}