奇怪的打印机的最小打印次数问题

题目描述

有一台奇怪的打印机，它有两个特性：

1. 每次打印时，打印机可以打印由同一个字符组成的连续序列
2. 在每次打印过程中，打印机可以在已经打印好的字符上覆盖打印新的字符

给定一个字符串 s，你的任务是找出打印出该字符串所需的最少打印次数。

示例

• 输入：s = "aaabbb"

• 输出：2

• 解释：先打印 "aaa"，然后打印 "bbb"

• 输入：s = "aba"

• 输出：2

• 解释：先打印 "aaa"，然后在中间位置打印 'b' 覆盖掉 'a'

解题思路

这个问题可以使用区间动态规划来解决。我们需要找到打印整个字符串 s 的最小打印次数。

定义状态
定义 dp[i][j] 表示打印子串 s[i...j] 所需的最小打印次数。

状态转移方程

1. 基础情况：当 i == j 时，dp[i][j] = 1（单个字符只需要打印一次）

2. 一般情况：对于区间 [i, j]

   • 如果 s[i] == s[j]，那么我们可以先打印 s[i] 字符覆盖整个区间，然后再处理中间部分
   • 如果 s[i] != s[j]，那么我们需要找到最优的分割点

更具体地说：

• 如果 s[i] == s[j]，那么 dp[i][j] = dp[i][j-1]
  因为我们可以先打印 s[i] 覆盖整个区间，然后中间部分与处理 [i, j-1] 类似
• 如果 s[i] != s[j]，那么我们需要在区间 [i, j] 中找到一个分割点 k，使得：
  dp[i][j] = min(dp[i][k] + dp[k+1][j])，其中 i ≤ k < j

详细解题步骤

让我们通过示例 s = "aba" 来理解这个过程：

1. 初始化：创建 dp 表格，对角线元素为 1

   • dp[0][0] = 1, dp[1][1] = 1, dp[2][2] = 1

2. 处理长度为 2 的子串：

   • 子串 "ab"：s[0] != s[1]，dp[0][1] = min(dp[0][0] + dp[1][1]) = 1 + 1 = 2
   • 子串 "ba"：s[1] != s[2]，dp[1][2] = min(dp[1][1] + dp[2][2]) = 1 + 1 = 2

3. 处理长度为 3 的子串 "aba"：

   • s[0] == s[2] ('a' == 'a')，所以 dp[0][2] = dp[0][1] = 2
   • 验证：先打印 "aaa"，然后在位置 1 打印 'b'

算法实现

def strangePrinter(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    
    # 创建 DP 表
    dp = [[0] * n for _ in range(n)]
    
    # 初始化：单个字符需要打印一次
    for i in range(n):
        dp[i][i] = 1
    
    # 按子串长度从小到大处理
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            # 情况1：首尾字符相同
            if s[i] == s[j]:
                dp[i][j] = dp[i][j-1]
            else:
                # 情况2：首尾字符不同，需要找到最优分割点
                dp[i][j] = float('inf')
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
    
    return dp[0][n-1]

复杂度分析

• 时间复杂度：O(n³)，需要三层循环
• 空间复杂度：O(n²)，用于存储 DP 表

优化思路

实际上，我们可以进一步优化状态转移方程。当 s[i] == s[j] 时，有更精确的表达式：
dp[i][j] = min(dp[i][k] + dp[k+1][j])，其中 k 满足 s[k] == s[i]

这样可以避免不必要的计算，但最坏情况下时间复杂度仍然是 O(n³)。

这个问题的关键在于理解：当首尾字符相同时，我们可以利用打印的覆盖特性来减少打印次数。