0664. 奇怪的打印机

• 标签：字符串、动态规划
• 难度：困难

题目链接

• 0664. 奇怪的打印机 - 力扣

题目大意

描述：有一台奇怪的打印机，有以下两个功能：

1. 打印机每次只能打印由同一个字符组成的序列，比如："aaaa"、"bbb"。
2. 每次可以从起始位置到结束的任意为止打印新字符，并且会覆盖掉原有字符。

现在给定一个字符串 $s$。

要求：计算这个打印机打印出字符串 $s$ 需要的最少打印次数。

说明：

• $1 \le s.length \le 100$。
• $s$ 由小写英文字母组成。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

对于字符串 $s$，我们可以先考虑区间 $[i, j]$ 上的子字符串需要的最少打印次数。

1. 如果区间 $[i, j]$ 内只有 $1$ 种字符，则最少打印次数为 $1$，即：$dp[i][i] = 1$。
2. 如果区间 $[i, j]$ 内首尾字符相同，即 $s[i] == s[j]$，则我们在打印 $s[i]$ 的同时我们可以顺便打印 $s[j]$，这样我们可以忽略 $s[j]$，只考虑剩下区间 $[i, j - 1]$ 的打印情况，即：$dp[i][j] = dp[i][j - 1]$。
3. 如果区间 $[i, j]$ 上首尾字符不同，即 $s[i] \ne s[j]$，则枚举分割点 $k$，将区间 $[i, j]$ 分为区间 $[i, k]$ 与区间 $[k + 1, j]$，使得 $dp[i][k] + dp[k + 1][j]$ 的值最小即为 $dp[i][j]$。

思路 1：动态规划

1. 划分阶段

按照区间长度进行阶段划分。

2. 定义状态

定义状态 $dp[i][j]$ 表示为：打印第 $i$ 个字符到第 $j$ 个字符需要的最少打印次数。

3. 状态转移方程

1. 如果 $s[i] == s[j]$，则我们在打印 $s[i]$ 的同时我们可以顺便打印 $s[j]$，这样我们可以忽略 $s[j]$，只考虑剩下区间 $[i, j - 1]$ 的打印情况，即：$dp[i][j] = dp[i][j - 1]$。
2. 如果 $s[i] \ne s[j]$，则枚举分割点 $k$，将区间 $[i, j]$ 分为区间 $[i, k]$ 与区间 $[k + 1, j]$，使得 $dp[i][k] + dp[k + 1][j]$ 的值最小即为 $dp[i][j]$，即：$dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])$。

4. 初始条件

• 初始时，打印单个字符的最少打印次数为 $1$，即 $dp[i][i] = 1$。

5. 最终结果

根据我们之前定义的状态，$dp[i][j]$ 表示为：打印第 $i$ 个字符到第 $j$ 个字符需要的最少打印次数。 所以最终结果为 $dp[0][size - 1]$。

思路 1：代码

class Solution:
    def strangePrinter(self, s: str) -> int:
        size = len(s)
        dp = [[float('inf') for _ in range(size)] for _ in range(size)]
        for i in range(size):
            dp[i][i] = 1
            
        for l in range(2, size + 1):
            for i in range(size):
                j = i + l - 1
                if j >= size:
                    break
                if s[i] == s[j]:
                    dp[i][j] = dp[i][j - 1]
                else:
                    for k in range(i, j):
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])

        return dp[0][size - 1]

思路 1：复杂度分析

• 时间复杂度：$O(n^3)$，其中 $n$ 为字符串 $s$ 的长度。
• 空间复杂度：$O(n^2)$。