String painter（区间DP）

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，每次操作可将一段任意区间变为一个字符，求由A变到B的最小操作次数。

#include <iostream>

#include <cstring>

#include <string>

#include <algorithm>

using namespace std;

int dp[][],ans[];///dp[i][j]中的i，j表示左右端点

int main()

{

    string a,b;

    while(cin>>a>>b)

    {

        memset(dp,,sizeof dp);

        for(int j=;b[j];j++)///预处理一段区间内的最小次数

            for(int i=j;i>=;i--)

            {

                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=;a[i];i++)

        {

            ans[i]=dp[][i];

            if(a[i]!=b[i])///找更少的次数

                for(int j=;j<i;j++)

                    ans[i]=min(ans[i],ans[j]+dp[j+][i]);

            else///不刷

                ans[i]=ans[i-];

        }

        cout<<ans[b.size()-]<<'\n';

    }

    return ;

}