664. 奇怪的打印机 难

664. 奇怪的打印机

有台奇怪的打印机有以下两个特殊要求：

• 打印机每次只能打印由 同一个字符 组成的序列。
• 每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。

给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

输入：s = “aba”
输出：2
解释：首先打印 “aaa” 然后在第二个位置打印 “b” 覆盖掉原来的字符 ‘a’。

//区间缩小，二维dp法，时间On^3，空间On^2
func strangePrinter(s string) int {
    n := len(s)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for i := n - 1; i >= 0; i-- {
        dp[i][i] = 1
        for j := i + 1; j < n; j++ {
            if s[i] == s[j] {                   // 即区间两端的字符相同
                dp[i][j] = dp[i][j-1]
            } else {
                dp[i][j] = math.MaxInt64        //取个最大值，啥意思？
                for k := i; k < j; k++ {        //那么我们需要分别完成该区间的左右两部分的打印,枚举
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])
                }
            }
        }
    }
    return dp[0][n-1]
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}