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?

zzzzzfzzzzz

abcdefedcba

abababababab

cdcdcdcdcdcd

6

7

区间dp，但是具体实现，没实现，参考了一下题解：链接：https://blog.csdn.net/martinue/article/details/45953229
代码:

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

#include<map>

#include<vector>

#include<cmath>

const int maxn=1e5+;

typedef long long ll;

using namespace std;

int a[],dp[][];

char s1[],s2[];

int solve(int i,int j)

{

    if(dp[i][j]!=-)

    return dp[i][j];

    if(i>j)

    return dp[i][j]=;

    if(i==j)

    return dp[i][j]=;

    dp[i][j]=solve(i+,j)+;

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

    if(s2[k]==s2[i])

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

    return dp[i][j];

}

int main ()

{

    while(cin>>s1>>s2)

    {

        memset(dp,-,sizeof(dp));memset(a,,sizeof(a));

        int len =strlen(s1);

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

        {

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

            int t=solve(i,j);

        }

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

        {

                a[i]=dp[][i];

            if(s1[i]==s2[i])

            {

                    if(i==)

                        a[i]=;

                    else

                    a[i]=a[i-];

            }

            else

            {

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

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

            }

        }

        printf("%d\n",a[len-]);

    }

    return ;

}