String painter_dp

Problem Description

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

 【题意】给出s1,s2两个字符串，求s1最少刷几次能变成s2，刷连续的一段区域，能覆盖。

【思路】先不管初始串，将目标串由空白串转变。dp[i][j]是i到j之间最少刷的次数。

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int N=110;
int dp[N][N],ans[N];
char s1[N],s2[N];

int main()
{
    while(scanf("%s %s",s1,s2)!=EOF)
    {
        int len=strlen(s1);
        memset(dp,0,sizeof(dp));
        
        for(int i=0;i<len;i++)
        {
            for(int j=i;j<len;j++)
                dp[i][j]=j-i+1;
        }
        for(int i=len-2;i>=0;i--)//空白串到目标串
        {
            for(int j=i+1;j<len;j++)
            {
                dp[i][j]=dp[i+1][j]+1;
                for(int k=i+1;k<=j;k++)
                {
                    if(s2[i]==s2[k])
                        dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j]);
                }
            }
        }
        for(int i=0;i<len;i++)
        {
            ans[i]=dp[0][i];
            if(s1[i]==s2[i])//如果初始串与目标串对应位置字符相同，根据所在位置分两种情况
            {
                if(i==0) ans[i]=0;
                else ans[i]=ans[i-1];//这个位置就不用考虑，刷的位置要么包含关系。要么分离关系，不可能相交，相交没有必要刷两遍。
            }
            for(int k=0;k<i;k++)
            {
                ans[i]=min(ans[i],ans[k]+dp[k+1][i]);
            }
            
        }
        cout<<ans[len-1]<<endl;
    }
    return 0;
}