奇怪的打印机 III

题目描述

有一个奇怪的打印机，它打印时每次可以连续打印一段相同颜色的字符，但每次打印会覆盖原来位置上已经存在的字符。现在给你一个字符串 s 表示目标字符串，打印机初始时是空白的（可以视为由无限个空格字符组成，但空格被视为无色）。每次操作，打印机可以选择任意起始位置和结束位置，以及一个颜色，将这段区间内所有字符都变成这个颜色。

现在的问题是：打印出目标字符串 s 最少需要多少次操作？

解题过程

这个问题可以用区间动态规划来解决。让我们一步步分析：

1. 问题分析

关键观察：

• 打印机每次操作可以覆盖任意连续区间
• 每次操作会将选定区间内所有字符变成同一种颜色
• 目标是最少操作次数打印出目标字符串

2. 状态定义

定义 dp[i][j] 表示打印出子串 s[i...j] 所需的最少操作次数。

3. 状态转移方程

情况1：如果 s[i] == s[j]

• 我们可以在同一次操作中打印这两个字符
• dp[i][j] = min(dp[i][j-1], dp[i+1][j])

情况2：如果 s[i] != s[j]

• 我们需要找到分割点 k，将区间分成两部分
• dp[i][j] = min(dp[i][k] + dp[k+1][j])，其中 i ≤ k < j

4. 边界条件

• 当 i > j 时，dp[i][j] = 0（空串不需要操作）
• 当 i == j 时，dp[i][j] = 1（单个字符需要一次操作）

5. 算法实现细节

我们需要按区间长度从小到大计算：

1. 先计算所有长度为1的区间
2. 然后计算长度为2的区间
3. 依此类推，直到计算整个字符串

6. 完整算法步骤

def strangePrinter(s: str) -> int:
    if not s:
        return 0
    
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    # 初始化长度为1的区间
    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] = min(dp[i][j-1], dp[i+1][j])
            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]

7. 示例分析

以字符串 "aaabbb" 为例：

• 长度为1：dp[0][0]=1, dp[1][1]=1, ..., dp[5][5]=1
• 长度为2：
  • [0,1]：s[0]=='a'==s[1]=='a'，dp[0][1]=min(dp[0][0], dp[1][1])=1
  • [4,5]：s[4]=='b'==s[5]=='b'，dp[4][5]=1
• 长度为6：[0,5]：s[0]=='a'≠s[5]=='b'
  • 尝试所有分割点，找到最小值为 dp[0][2]+dp[3][5]=1+1=2

最终结果为2次操作。

8. 时间复杂度优化

基础版本的时间复杂度是 O(n³)，可以通过预处理相同字符的区间来优化到接近 O(n²)。

关键理解点

• 首尾字符相同时，可以减少一次操作
• 问题本质是找到最优的分割方式
• 区间DP保证了我们考虑了所有可能的分割方案