奇怪的打印机问题（最小打印次数问题） 题目描述 有一个奇怪的打印机，每次操作可以打印一段连续的相同字符（例如， "aaa" 或 "bb" ），但打印新字符时会覆盖原有字符。给定一个字符串 s ，求打印机打印出 s 所需的最少操作次数。 示例 输入： s = "aaabbb" 输出： 2 解释：先打印 "aaa" ，再打印 "bbb" 。 输入： s = "aba" 输出： 2 解释：先打印 "aaa" ，再在第二个位置打印 "b" （覆盖原有的 a ）。 解题思路 问题分析 打印机的特性：每次打印连续相同字符，但新打印会覆盖旧字符。 关键观察：如果字符串首尾字符相同，可以 先打印整个字符串为同一字符 （匹配首尾字符），再逐步细化中间部分，从而减少操作次数。 若首尾字符不同，需将字符串拆分为两部分分别处理。 状态定义 设 dp[i][j] 表示打印子串 s[i:j] （包含 i 和 j ）所需的最小打印次数。 状态转移方程 情况1： s[i] == s[j] 首尾字符相同时，可以在打印 s[i] 时顺带打印 s[j] （因为打印是连续的）。 转移方程： dp[i][j] = dp[i][j-1] 解释：打印 s[i:j] 时，可以先打印 s[i] 覆盖整个区间（使整个区间变为 s[i] ），再细化 s[i+1:j-1] 。但更优策略是直接利用 s[i:j-1] 的打印方式，在最后一步扩展至 j 。 情况2： s[i] != s[j] 需要将区间拆分为两部分，枚举分割点 k （ i ≤ k < j ）： dp[i][j] = min(dp[i][k] + dp[k+1][j]) 解释：分别打印左半部分和右半部分，合并操作次数。 初始化与边界条件 单个字符只需一次打印： dp[i][i] = 1 。 区间长度从 2 开始逐步扩展。 计算顺序 按区间长度 len 从小到大计算（ len 从 1 到 n ）。 详细步骤（以 s = "aba" 为例） 初始化： dp[0][0] = 1 （ "a" ） dp[1][1] = 1 （ "b" ） dp[2][2] = 1 （ "a" ） 计算长度 len = 2 ： 子串 "ab" ： s[0] != s[1] ，枚举 k=0 ： dp[0][1] = min(dp[0][0] + dp[1][1]) = 1 + 1 = 2 子串 "ba" ： s[1] != s[2] ，枚举 k=1 ： dp[1][2] = min(dp[1][1] + dp[2][2]) = 1 + 1 = 2 计算长度 len = 3 ： 子串 "aba" ： s[0] == s[2] （均为 'a' ）， dp[0][2] = dp[0][1] ？需注意：正确转移应为 dp[i][j] = dp[i][j-1] 仅当首尾相同时成立。 但这里 dp[0][1] = 2 ，直接赋值会得到 2，但实际最优策略是： 先打印整个区间为 "aaa" （1次），再在中间打印 "b" （覆盖第2个字符），共 2 次。 验证：若按分割点枚举， k=0 ： dp[0][0] + dp[1][2] = 1 + 2 = 3 ； k=1 ： dp[0][1] + dp[2][2] = 2 + 1 = 3 。 但利用首尾相同特性，可直接得到 dp[0][2] = dp[0][1] = 2 。 最终结果： dp[0][2] = 2 。 算法实现要点 需确保在 s[i] == s[j] 时直接取 dp[i][j-1] ，避免不必要的分割。 时间复杂度：O(n³)（枚举区间和分割点），但可通过优化减少常数。 总结 此问题核心在于利用首尾字符相同的特性减少操作次数，体现了区间动态规划中“状态转移依赖子区间”和“贪心优化”的结合。