HDU 2476 String painter （*区间DP+基础Dp）

H - String painter

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

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

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

1~9刷一次，abbbbbbbbba

2~8:abcccccccba

3~7:abcdddddcba

4~6:abcdeeedcab

5:abcdefedcab

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

第二个样例也一样

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

1~9刷一次，cdddddddddcb

2~8:cdcccccccdcb

3~7:cdcdddddcdcb

4~6:cdcdcccdcdcb

5:cdcdcdcdcdcb

最后竟串尾未处理的刷一次

就变成了串2cdcdcdcdcdcd

所以一共7次

题解：

（1）子问题分析：

其实这道题无非是两种情况，(1)a串与b串对于位置i字符是一样的，这样就直接用前一个字符的需要修改的次数就好了，当前i字母不用刷

(2)a串和b串对应位置不同，也就是当前位置是需要刷的，这样怎么刷？好像没有规律了，不过唯一可以降低步数的可能是存在t[i] == t[k]，因为这种情况下可能是不用刷的正确的处理方法是通过分割，就是前0-k个采取最优的刷法，k+1~i个采取爆刷的方式，就是不管a串对应的如何，直接对bk+1~i位置采用最少的步数刷（也就是下面的dp[][]）,然后对每个分割点取最小值，还是有点抽象，但是结果是正确的，以后在深究。所以在真正算之前还需要预处理b串区间爆刷的步数，也就是本问题需要做两次DP，先预处理，再真正DP

（2）状态：

dp[i][j]为str2从空刷为i~j的刷法，也可以想为对于同等区段的str1，不管str1是什么，直接刷为对应的str2串

ans[i] 从0~i需要刷的最小步数，使其和b串一样

（3）状态转移方程：

预处理：dp[i][j] = min(dp[i][j],(dp[i+1][k]+dp[k+1][j]));///i与k相同，寻找i刷到k的最优方案

求结果：ans[i] = min(ans[i],ans[j]+dp[j+1][i]);///寻找j来分割区间得到最优解

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

char str1[105],str2[105];
int dp[105][105];///dp[i][j]为str2从空刷为i~j的刷法，也可以想为对于同等区段的str1，不管str1是什么，直接刷为对应的str2串
int ans[105],i,j,k,len;

int main()
{
    while(~scanf("%s%s",str1,str2))
    {
        len = strlen(str1);
        memset(dp,0,sizeof(dp));
        for(j = 0; j<len; j++)
        {
            for(i = j; i>=0; i--)///j为尾，i为头
            {
                dp[i][j] = dp[i+1][j]+1;///先每个单独刷
                for(k = i+1; k<=j; k++)///i到j中间所有的刷法
                {
                    if(str2[i]==str2[k])
                        dp[i][j] = min(dp[i][j],(dp[i+1][k]+dp[k+1][j]));///i与k相同，寻找i刷到k的最优方案
                }
            }
        }
        for(i = 0; i<len; i++)
            ans[i] = dp[0][i];///根据ans的定义先初始化
        for(i = 0; i<len; i++)
        {
            if(str1[i] == str2[i])
                ans[i] = ans[i-1];///如果对应位置相等，这个位置可以不刷
            else
            {
                for(j = 0; j<i; j++)
                    ans[i] = min(ans[i],ans[j]+dp[j+1][i]);///寻找j来分割区间得到最优解
            }
        }
        printf("%d
",ans[len-1]);
    }

    return 0;
}