LeetCode 664. 奇怪的打印机（区间DP）

示例 1：
输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa" 然后打印 "bbb"。

示例 2：
输入：s = "aba"
输出：2
解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。
 
提示：
1 <= s.length <= 100
s 由小写英文字母组成

class Solution {
public:
    int strangePrinter(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
        for(int i = 0; i < n; ++i)
            dp[i][i] = 1; // 初始情况
        for(int j = 1; j < n; ++j)
        {
            for(int i = j-1; i >= 0; --i)
            {
                if(s[i] == s[j]) // 两端的字符一样
                    dp[i][j] = dp[i][j-1]; // j 字符 可以 跟 i 一同打印
                else // 两端不一样，枚举区间的中间切分点
                {
                    for(int k = i; k < j; ++k)
                    {
                        dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]);
                    }
                }
            }
        }
        return dp[0][n-1];
    }
};