奇怪的打印机 题目描述 有一台奇怪的打印机，它有两个特殊的功能： 每次操作，打印机可以打印一段连续的相同字符 每次操作，打印机可以在已经打印好的字符上覆盖新的字符，但只能覆盖连续的一段字符 给定一个字符串 s，你的任务是找出打印机打印出字符串 s 所需的最少操作次数。 示例 输入：s = "aaabbb" 输出：2 解释：首先打印 "aaa"，然后打印 "bbb" 输入：s = "aba" 输出：2 解释：首先打印 "aaa"，然后在中间位置覆盖打印 "b" 解题思路 这个问题可以使用区间动态规划来解决。我们需要找到打印整个字符串 s 的最小操作次数。 关键观察 如果字符串首尾字符相同，那么我们可以先打印整个区间为这个字符，然后处理中间部分 如果字符串首尾字符不同，我们需要考虑所有可能的分割点 动态规划定义 定义 dp[ i][ j] 表示打印子串 s[ i...j ] 所需的最小操作次数。 状态转移方程 基础情况 ：当 i == j 时，dp[ i][ j ] = 1（单个字符只需要一次操作） 当 s[ i] == s[ j] 时 ： 我们可以先打印整个区间为 s[ i ] 字符，然后处理内部 dp[ i][ j] = dp[ i][ j-1] 或 dp[ i+1][ j ] 因为首尾相同，打印最后一个字符时可以"顺便"打印第一个字符 当 s[ i] != s[ j] 时 ： 我们需要在区间内找一个分割点 k dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j])，其中 i ≤ k < j 详细解题步骤 让我们通过示例 s = "aba" 来详细说明： 步骤1：初始化 创建 dp 表格，大小为 n × n（n = 3） 对角线元素初始化为 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 解释：先打印整个区间为 'a'（一次操作），然后在中间覆盖打印 'b'（第二次操作） 最终结果 ：dp[ 0][ 2 ] = 2 算法实现要点 按区间长度从小到大计算 先处理小区间，再处理大区间 注意边界条件处理 时间复杂度 ：O(n³) 空间复杂度 ：O(n²) 这个算法通过动态规划有效地解决了打印机的最少操作次数问题，核心思想是利用区间DP逐步构建最优解。