奇怪的打印机

[louzhedong]

习题

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

打印机每次只能打印由 同一个字符 组成的序列。
每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。
给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

示例 1：

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

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

提示：

1 <= s.length <= 100
s 由小写英文字母组成

思路

本题我们可以采用动态规划的方式来解答

假设用dp[i][j] 来表示 打印第i个字符到第j个字符需要的次数

当i == j 时，j 可以顺便和 i 一起打印，最小的打印次数即为 dp[i][j - 1]

当i != j 时，我们将字符串分为两部分，分别打印。

假设中间分隔的字符串是第k个，那对于单次来说，最小的次数未dp[i][k] + dp[k + 1][j]的和，遍历k，算出所有可能性中最小的那种

解答

javascript

/**
 * @param {string} s
 * @return {number}
 */
var strangePrinter = function(s) {
    var len = s.length;
    var dp = [];
    for (var i = 0; i < len; i ++) {
        dp[i] = [];
    }

    for (var i = len - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (var j = i + 1; j < len; j++) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i][j - 1]
            } else {
                var min = Number.MAX_SAFE_INTEGER;
                for (var k = i; k < j; k++) {
                    min = Math.min(min, dp[i][k] + dp[k + 1][j]);
                }
                dp[i][j] = min;
            }
        }
    }
    return dp[0][len - 1];
};

go

func strangePrinter(s string) int {
    n := len(s)
    dp := make([][]int, n)
    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 {
                min_value := math.MaxInt64
                for k := i; k < j; k++ {
                    min_value = min(min_value, dp[i][k] + dp[k + 1][j])
                }
                dp[i][j] = min_value
            }
        }
    }
    return dp[0][n - 1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}