奇怪的打印机问题 题目描述 有一台奇怪的打印机，它有两个特性： 每次打印时，只能打印连续相同字符的序列 每次打印可以在任意位置开始和结束，覆盖之前已经存在的字符 给定一个字符串 s，你的任务是找出打印机打印出该字符串所需的最少打印次数。 示例 输入：s = "aaabbb" 输出：2 解释：先打印 "aaa"，然后打印 "bbb" 输入：s = "aba" 输出：2 解释：先打印 "aaa"，然后在中间位置打印 "b" 覆盖第二个 'a' 解题思路 这个问题可以使用区间动态规划来解决。我们需要找到打印整个字符串 s 的最少次数。 状态定义 定义 dp[ i][ j] 表示打印子串 s[ i...j ] 所需的最少打印次数。 状态转移方程 基础情况 ：当区间长度为 1 时，dp[ i][ i ] = 1 一般情况 ：对于区间 [ i, j ]，我们考虑： 如果 s[ i] == s[ j]：我们可以先打印整个区间为 s[ i ] 字符，然后再处理中间部分 如果 s[ i] != s[ j ]：我们需要将区间分割成两部分分别处理 具体的状态转移： 情况1：s[ i] == s[ j ] dp[ i][ j] = min(dp[ i][ j-1], dp[ i+1][ j ]) 解释：当首尾字符相同时，打印最后一个字符时可以顺便打印第一个字符，或者打印第一个字符时顺便打印最后一个字符 情况2：s[ i] != s[ j ] dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j])，其中 i ≤ k < j 解释：当首尾字符不同时，我们需要找到最优的分割点，将区间分成两部分分别处理 详细解题步骤 让我们通过示例 s = "aba" 来详细说明： 步骤1：初始化 dp[ 0][ 0 ] = 1 (打印 "a") dp[ 1][ 1 ] = 1 (打印 "b") dp[ 2][ 2 ] = 1 (打印 "a") 步骤2：处理长度为2的区间 区间 [ 0,1 ]："ab" s[ 0] != s[ 1]，所以 dp[ 0][ 1] = min(dp[ 0][ 0] + dp[ 1][ 1 ]) = 1 + 1 = 2 区间 [ 1,2 ]："ba" s[ 1] != s[ 2]，所以 dp[ 1][ 2] = min(dp[ 1][ 1] + dp[ 2][ 2 ]) = 1 + 1 = 2 步骤3：处理长度为3的区间 区间 [ 0,2 ]："aba" s[ 0] == s[ 2 ] ('a' == 'a') dp[ 0][ 2] = min(dp[ 0][ 1], dp[ 1][ 2 ]) = min(2, 2) = 2 最终结果 ：dp[ 0][ 2 ] = 2 算法实现要点 按区间长度从小到大处理 对于每个区间 [ i, j ]，根据首尾字符是否相同选择不同的转移策略 时间复杂度：O(n³)，空间复杂度：O(n²) 优化思路 实际上，当 s[ i] == s[ j] 时，我们可以有更优的策略：dp[ i][ j] = dp[ i][ j-1 ] 因为我们可以先打印整个区间为 s[ i ] 字符，然后只处理中间不同的部分，这样通常比分割区间更优。 这个问题的关键在于理解：当首尾字符相同时，我们可以在一次打印中完成首尾字符的打印，从而减少打印次数。