奇怪的打印机 II

题目描述
有一台奇怪的打印机，每次操作可以打印一段连续的相同字符。打印时，新打印的字符会覆盖原来位置上已经存在的字符。给定一个字符串 s，表示目标字符串，问至少需要多少次操作才能打印出 s？
例如：

• 输入 s = "aaabbb"，输出为 2（先打印 "aaa"，再打印 "bbb"）。
• 输入 s = "aba"，输出为 2（先打印 "aaa"，再在中间位置打印 'b' 覆盖掉中间的 'a'）。

解题思路
这个问题是区间动态规划的经典应用。我们需要考虑如何将字符串拆分成子区间，并利用子区间的最优解来推导整个区间的最优解。

步骤分解

1. 定义状态
   设 dp[i][j] 表示打印出字符串 s[i:j+1]（即从索引 i 到 j 的子串）所需的最少操作次数。

2. 状态转移分析

   • 情况1：如果子串长度为 1（即 i == j），那么只需要一次操作，即 dp[i][j] = 1。
   • 情况2：对于更长的子串，考虑两种情况：
     • 分段处理：将子串分成两部分，分别打印，即 dp[i][j] = min(dp[i][k] + dp[k+1][j])，其中 k 从 i 到 j-1。
     • 整体处理：如果 s[i] == s[j]，说明在打印 s[i] 时可以直接延伸到 s[j] 的位置（因为打印机可以连续打印相同字符），此时 dp[i][j] = dp[i][j-1]。为什么？因为打印 s[i] 时已经覆盖了 s[j] 的位置，后续只需处理中间部分。

3. 递推顺序
   由于长区间依赖于短区间的结果，我们需要按区间长度从小到大进行递推。

示例推导
以 s = "aba" 为例：

1. 初始化长度为 1 的区间：
   • dp[0][0] = 1, dp[1][1] = 1, dp[2][2] = 1。
2. 长度为 2 的区间：
   • "ab"：dp[0][1] = min(dp[0][0] + dp[1][1]) = 2（分段打印），且 s[0] != s[1]，无法整体处理。
   • "ba"：同理，dp[1][2] = 2。
3. 长度为 3 的区间 "aba"：
   • 分段处理：尝试所有分割点：
     • k=0：dp[0][0] + dp[1][2] = 1 + 2 = 3
     • k=1：dp[0][1] + dp[2][2] = 2 + 1 = 3
   • 整体处理：因为 s[0] == s[2] == 'a'，所以 dp[0][2] = dp[0][1] = 2（这里 dp[0][1] 表示处理 "ab" 的最小次数，但注意在整体处理时，打印第一个 'a' 时已经覆盖了第三个 'a'，中间部分 "b" 需要额外处理）。实际上更准确的是：dp[i][j] = dp[i][j-1] 当 s[i] == s[j] 时成立，因为最后一个字符可以被第一次操作覆盖。

最终状态转移方程

dp[i][j] = min(
    dp[i][k] + dp[k+1][j]  for k in [i, j-1],
    dp[i][j-1] if s[i] == s[j]  # 关键优化
)

初始条件：当 i == j 时，dp[i][j] = 1。

复杂度分析

• 时间复杂度：O(n³)，需要三重循环（区间长度、起点、分割点）。
• 空间复杂度：O(n²)，用于存储 dp 表。

通过这种区间动态规划的方法，我们可以高效地计算出打印任意字符串所需的最小操作次数。