题目链接：https://vjudge.net/contest/308310#problem/H
题目大意：给出两个字符串，每次我们可以把一个字符串的一个区间刷成同一个字母（每次修改区间[L, R]全部为同一个字符），问最少多少步可以把第一个字符串变为第二个字符串。

例如zzzzzfzzzzz，长度为11，我们就将下标看做0~10

先将0~10刷一次，变成aaaaaaaaaaa

1~9刷一次，abbbbbbbbba

2~8:abcccccccba

3~7:abcdddddcba

4~6:abcdeeedcab

5:abcdefedcab

这样就6次，变成了s2串了

思路：此题分两步，第一步是假设由空串变成b串，进行区间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])。

然后用ans[i]:代表把前i个a[i]字符刷成b。需要的最小步数。

for(int i=1;i<=n;i++)
{
   if(s1[i]==s2[i])
   {
       ans[i]=ans[i-1];
   }
   else
   {
       for(int k=1;k<i;k++)
       {
           ans[i]=min(ans[i], ans[k]+dp[k+1][i]);
       }
   }
}

全部代码：

#include <bits/stdc++.h>
using namespace std;

char s1[105];
char s2[105];
int dp[105][105];
int ans[105];
int main()
{
    while(scanf("%s",s1+1)!=EOF)
    {
        memset(dp, 0, sizeof(dp));
        memset(ans, 0, sizeof(ans));
        scanf("%s", s2+1);
        int n=strlen(s1+1);

        for(int Len=1;Len<=n;Len++)
        {
            for(int L=1;L+Len-1<=n;L++)
            {
                int R=L+Len-1;
                dp[L][R]=dp[L+1][R]+1;

                for(int k=L+1;k<=R;k++)//枚举可能相等的位置
                {
                    if(s2[L]==s2[k])
                    {
                        dp[L][R]=min(dp[L][R], dp[L+1][k]+dp[k+1][R]);
                    }
                }
            }

        }

        ans[0]=0;
        for(int i=1;i<=n;i++)
        {
            ans[i]=dp[1][i];
        }

        for(int i=1;i<=n;i++)
        {
            if(s1[i]==s2[i])
            {
                ans[i]=ans[i-1];
            }
            else
            {
                for(int k=1;k<i;k++)
                {
                    ans[i]=min(ans[i], ans[k]+dp[k+1][i]);
                }
            }
        }

        printf("%d\n",ans[n]);
    }

    return 0;
}