难度: Hard
有台奇怪的打印机有以下两个特殊要求：
给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。
示例 1：
输入：s = "aaabbb" 输出：2 解释：首先打印 "aaa" 然后打印 "bbb"。
示例 2：
输入：s = "aba" 输出：2 解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。
提示：
1 <= s.length <= 100s 由小写英文字母组成运行时间: 131 ms
内存: 18.6 MB
class Solution:
def strangePrinter(self, s: str) -> int:
stack = []
for i, c in enumerate(s):
if not stack or stack[-1] != c:
stack.append(c)
s = ''.join(stack)
last_seen = [-1] * 26
prev = [-1] * len(s)
for i, c in enumerate(s):
prev[i] = last_seen[ord(c) - ord('a')]
last_seen[ord(c) - ord('a')] = i
@cache
def dp(i: int, j: int) -> int:
if i >= j - 1:
return j - i
if s[i] == s[j - 1]:
return dp(i, j - 1)
min_ = 100
k = j - 1
while k > i: # 只在和最后字符相同的字符下标分割
min_ = min(dp(i, k) + dp(k, j), min_)
k = prev[k]
return min_
return dp(0, len(s))
该题解采用了动态规划的思路。首先对原字符串进行预处理，去除连续重复的字符。然后使用记忆化搜索来求解最少打印次数。dp(i, j) 表示打印子串 s[i:j] 所需的最少次数。如果 s[i] 和 s[j-1] 相同，则可以直接忽略最后一个字符。否则，枚举 s[i:j] 中间与 s[j-1] 相同的字符作为分割点，将原问题分解为两个子问题，取各子问题的最优解，然后相加得到原问题的最优解。通过记忆化搜索避免了重复计算。
时间复杂度: O(n^3)
空间复杂度: O(n^2)
class Solution:
def strangePrinter(self, s: str) -> int:
# 预处理，去除连续重复的字符
stack = []
for i, c in enumerate(s):
if not stack or stack[-1] != c:
stack.append(c)
s = ''.join(stack)
# 记录每个字符最后一次出现的位置
last_seen = [-1] * 26
prev = [-1] * len(s)
for i, c in enumerate(s):
prev[i] = last_seen[ord(c) - ord('a')]
last_seen[ord(c) - ord('a')] = i
@cache
def dp(i: int, j: int) -> int:
if i >= j - 1:
return j - i
if s[i] == s[j - 1]:
return dp(i, j - 1)
min_ = 100
k = j - 1
while k > i: # 只在和最后字符相同的字符下标分割
min_ = min(dp(i, k) + dp(k, j), min_)
k = prev[k]
return min_
return dp(0, len(s))
在题解中，预处理步骤去除连续重复的字符是因为在打印过程中，连续的相同字符可以在一次打印操作中完成。例如，字符串'aaabb'可以被看作是'ab'进行打印，因为连续的'a'和'b'在实际打印中不需要单独区分。这样预处理后，可以显著减少需要考虑的子问题数量，从而简化问题的复杂度。这个步骤有助于优化动态规划过程中的状态转移，减少不必要的冗余计算。
在动态规划中，当s[i]和s[j-1]相同时，意味着第i个字符和第j-1个字符可以在同一次打印操作中被打印出来，因此s[j-1]可以被's[i...j-1]'的打印过程包含。因此，问题可以简化为求解s[i...j-2]的最小打印次数，即dp(i, j-1)。这利用了问题的重叠子问题特性，避免了重复的计算，且保证了打印次数最小化。
记忆化搜索是动态规划的一种实现方式，它通过存储已经计算过的结果（通常是在递归过程中）来避免重复计算，从而提高效率。在Python中，这通常是通过使用装饰器如@cache来实现的。这种方法与普通递归的主要区别在于，普通递归每次调用都会重新计算结果，而记忆化搜索会先查看之前是否已经计算过相同的调用，如果是，则直接返回存储的结果，减少了计算次数。
数组prev的作用是帮助快速定位一个字符上一次出现的位置，从而在动态规划过程中有效地找到可能的分割点。当动态规划考虑将字符串分割为两部分以求解最小打印次数时，知道一个字符上次出现的位置可以直接跳到那个位置，而不需要逐个检查每个字符。这样可以减少不必要的迭代，优化算法的时间效率。