区间动态规划例题：奇怪的打印机

题目描述
有一个奇怪的打印机，每次打印时可以选择打印一段连续的相同字符，但每次打印会覆盖原有位置的内容。给定一个字符串 s，打印机初始状态为空白（即所有位置为空白字符）。问至少需要多少次打印操作才能打印出目标字符串 s？

示例
输入：s = "aaabbb"
输出：2
解释：先打印 "aaa"，再打印 "bbb"。
输入：s = "aba"
输出：2
解释：先打印 "aaa"（覆盖全部位置），再打印 'b' 覆盖第二个位置；或先打印整个字符串 "aba"，再局部修正。

解题思路

1. 问题分析

   • 打印机的特性：每次操作可以打印一段连续区间内的相同字符，但会覆盖该区间原有内容。
   • 目标：用最少操作次数打印出目标字符串。
   • 关键观察：如果字符串首尾字符相同，那么打印首尾时可能在一次操作中完成（延伸覆盖中间部分）。

2. 定义状态

   • 设 dp[i][j] 表示打印子串 s[i:j]（包含端点）所需的最少打印次数。
   • 目标：求 dp[0][n-1]，其中 n 为字符串长度。

3. 状态转移

   • 基础情况：当区间长度为 1 时（即 i == j），只需 1 次打印，即 dp[i][i] = 1。
   • 一般情况（i < j）：
     • 情况1：如果 s[i] == s[j]，可以在打印 s[i] 时一次性覆盖到位置 j（因为打印机允许连续相同字符），此时 dp[i][j] = dp[i][j-1]。
       • 解释：打印 s[i] 时直接延伸到 j，右侧部分 j 无需额外操作。
     • 情况2：如果 s[i] != s[j]，需要将区间分割为两部分，枚举分割点 k（i ≤ k < j）：

\[ dp[i][j] = \min_{k \in [i, j-1]} \left( dp[i][k] + dp[k+1][j] \right) \]

   - 解释：分别完成左右两部分的打印，合并操作次数。  

• 优化观察：如果区间内存在多个相同字符，首次打印时尽可能延长相同字符的区间，减少后续操作。但通过上述两种情况已覆盖最优解。

4. 递推顺序
   • 按区间长度从小到大计算：先计算所有长度为 1 的区间，再计算长度为 2、3...直到 n。

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

1. 初始化单字符区间：
   • dp[0][0] = 1, dp[1][1] = 1, dp[2][2] = 1。
2. 长度 2 的区间：
   • [0,1]（"ab"）：s[0] != s[1]，枚举 k=0：dp[0][0] + dp[1][1] = 2。
   • [1,2]（"ba"）：同理得 dp[1][2] = 2。
3. 长度 3 的区间 [0,2]（"aba"）：
   • s[0] == s[2]（均为 'a'），所以 dp[0][2] = dp[0][1]？
     • 注意：这里不能直接取 dp[0][1]，因为 dp[0][1] 是 2，但实际最优解是 2（先打全 "aaa"，再改中间为 'b'）。
     • 正确做法：当 s[0] == s[2]，可视为打印 s[0] 时覆盖到位置 2，但中间字符 s[1] 可能不同，因此需考虑区间分割：

\[ dp[0][2] = \min(dp[0][1], dp[1][2], dp[0][0] + dp[1][2], dp[0][1] + dp[2][2]) \]

   实际上，更高效的处理是：  
   - 如果 `s[i] == s[j]`，则 `dp[i][j] = dp[i][j-1]`（因为打印 `s[i]` 时可延伸到 `j`，无需额外操作）。  
   - 验证：`dp[0][2] = dp[0][1] = 2`。  
   但需注意：如果中间字符与两端相同，可能进一步减少次数。通用规则为：  

\[ dp[i][j] = \min(dp[i][k] + dp[k+1][j] - 1) \quad \text{若} \ s[i] = s[k+1] \]

   简化后，标准解法是：  
   - 初始化 `dp[i][j] = dp[i][j-1] + 1`（默认最后字符单独打印）。  
   - 若 `s[k] == s[j]`（`i ≤ k < j`），则：  

\[ dp[i][j] = \min(dp[i][j], dp[i][k] + dp[k+1][j-1]) \]

   但更常见的简洁写法是：  

\[ dp[i][j] = \begin{cases} dp[i][j-1] & \text{if } s[i] == s[j] \\ \min_{i \leq k < j} (dp[i][k] + dp[k+1][j]) & \text{otherwise} \end{cases} \]

   对于 `"aba"`：  
   - `s[0] == s[2]`，所以 `dp[0][2] = dp[0][1] = 2`。  

最终结果：dp[0][2] = 2，符合示例。

总结

• 核心思路：区间 DP 通过首尾字符是否相同优化分割策略。
• 时间复杂度：O(n³)，空间复杂度：O(n²)。
• 关键：首尾相同时可减少一次操作，直接继承子区间结果。