String painter（HDU-2476）| 区间dp

题意：
给出两长度相同的字符串，每次操作可以把第一个字符串的一段区间内的所有字母都换成同一个字母，现要将第一个字符串转换成第二个，求最少执行多少次操作
分析：

• 通过区间的第一个点将区间分成两部分
• 用 dp[i][j] 来表示在区间 i~j 内操作的最少次数，先对字符串2进行处理，假设第 i 个字符需要操作一次，则有 dp[i][j]=dp[i+1][j]+1，在区间 i~j 内，若第 k 个字符与第 i 个相同，则可以将区间 i~j 分成两部分 dp[i][j]=min(dp[i+1][k]+dp[k+1][j]);
  代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 1e2 + 10;
const int inf = 0x3f3f3f3f;
int dp[maxn][maxn];
int sum[maxn];
char a[maxn], b[maxn];
int n;

int main()
{
    while(cin >> (a + 1) >> (b + 1))
    {
        int n = strlen(a + 1);
        for(int i = 1; i <= n; i++) dp[i][i] = 1;
        for(int len = 2; len <= n; len++)
            for(int i = 1; i <= n; i++)
            {
                int j = i + len - 1;
                if(j > n) continue;
                dp[i][j] = dp[i + 1][j] + 1;
                for(int k = i + 1; k <= j; k++)
                    if(b[k] == b[i])
                        dp[i][j] = min(dp[i][j], dp[i + 1][k] + dp[k + 1][j]);
            }
        for(int i = 1; i <= n; i++)
        {
            if(a[i] == b[i]) sum[i] = sum[i - 1];
            else
            {
                sum[i] = sum[i - 1] + 1;
                for(int k = 1; k <= i - 1; k++)
                    sum[i] = min(sum[i], sum[k - 1] + dp[k][i]);
            }
        }
        cout << sum[n] << endl;
    }
}