奇怪的打印机 III 题目描述 有一个奇怪的打印机，它打印时遵循以下特殊规则： 每次操作可以从任意位置开始到任意位置结束打印一串相同的字符 每次打印会覆盖原有位置上已经存在的字符 打印机初始状态为白纸（可以认为是空字符串） 给定目标字符串s，求打印出目标字符串所需的最少操作次数 例如： 输入：s = "aaabbb" 输出：2 解释：先打印"aaa"，再打印"bbb" 解题过程 步骤1：理解问题本质 这个问题要求我们找到最少的打印次数来构造目标字符串。关键观察点： 每次打印只能打印一种字符 新打印会完全覆盖之前打印的内容 我们需要找到最优的打印顺序 步骤2：定义状态 定义dp[ i][ j]表示打印子串s[ i...j ]所需的最少操作次数。 步骤3：分析基础情况 当i = j时，即单个字符，只需要1次操作：dp[ i][ i ] = 1 当i > j时，空子串，需要0次操作 步骤4：状态转移分析 考虑子串s[ i...j ]，有两种情况： 情况1：如果s[ i] = s[ j ] 我们可以先打印整个区间为s[ i ]的颜色，然后再处理中间部分： 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 步骤5：状态转移方程 综合以上分析： dp[ i][ i ] = 1 对于i < j： 如果s[ i] == s[ j]：dp[ i][ j] = min(dp[ i][ j-1], dp[ i+1][ j ]) 如果s[ i] ≠ s[ j]：dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j ])，其中k从i到j-1 步骤6：实现细节 使用双重循环，外层循环枚举区间长度，内层循环枚举起始位置 采用自底向上的填表方式 步骤7：示例分析 以s = "aaabbb"为例： 初始化： dp[ 0][ 0] = 1, dp[ 1][ 1] = 1, ..., dp[ 5][ 5 ] = 1 长度2： "aa": dp[ 0][ 1] = min(dp[ 0][ 0], dp[ 1][ 1 ]) = 1 "ab": dp[ 1][ 2] = min(dp[ 1][ 1]+dp[ 2][ 2 ]) = 2 依此类推... 最终dp[ 0][ 5 ] = 2，与预期一致。 步骤8：算法复杂度 时间复杂度：O(n³)，其中n为字符串长度 空间复杂度：O(n²) 这个解法通过区间动态规划系统地考虑了所有可能的分割方式，确保了找到最优的打印策略。