奇怪的打印机 题目描述 有一台奇怪的打印机，它每次打印时都会将 从某个起始位置到某个结束位置 的所有字符都打印成 同一个字符 。打印机初始时没有任何字符，每次打印操作都会覆盖掉对应位置上已有的字符（如果该位置之前已经有字符的话）。 给定一个字符串 s ，你的任务是计算出打印机打印出这个字符串所需的最少打印次数。 示例 输入：s = "aaabbb" 输出：2 解释：首先打印 "aaaaaa"，然后从第四个位置开始打印 "bbb"，覆盖掉原有的 'a'，得到 "aaabbb"。 输入：s = "aba" 输出：2 解释：首先打印 "aaa"，然后在第二个位置打印 'b'，覆盖掉第二个位置的 'a'，得到 "aba"。另一种方案是先打印整个字符串 "aaa"，然后在第二个位置打印 'b'，但这样需要三次操作（先打印aaa，再在第二个位置打印b，这实际上也是两次操作？这里需要澄清：一次操作是打印一个连续的区间为同一个字符。所以方案1：第一次打印"aaa"，第二次在第二个位置打印一个字符'b'（覆盖），得到"aba"，这需要两次操作。方案2：第一次打印整个"aaa"，第二次在第二个位置打印一个字符'b'，这仍然是两次操作。实际上，对于"aba"，最少需要两次操作。先打印"aaa"（一次），再在第二个位置打印"b"（一次），总共两次。如果先打印整个字符串"aaa"（一次），再在第二个位置打印"b"（这算一次操作，覆盖了第二个字符），结果也是"aba"，两次。所以答案是2。 解题思路 这个问题可以使用区间动态规划来解决。我们定义 dp[i][j] 为打印出字符串 s 中从第 i 个字符到第 j 个字符（闭区间）的子串所需的最少打印次数。 第一步：分析区间两端字符的关系 基础情况 ：当区间长度为 1，即 i == j 时，只需要一次打印操作就能打印出这个单独的字符。所以， dp[i][i] = 1 。 状态转移的关键洞察 ：考虑一个区间 [i, j] 。 情况一 ：如果区间两端的字符相同，即 s[i] == s[j] 。我们可以在第一次打印操作时，就将整个区间 [i, j] 都打印成 s[i] （也就是 s[j] ）。那么，在完成这次操作后，区间两端的字符已经正确了。我们接下来只需要关心如何打印区间内部的字符即可。但是，由于第一次操作已经将整个区间都刷成了 s[i] ，我们其实可以 将整个区间视为在第一次操作的基础上，去完成内部子区间 [i, j-1] 或 [i+1, j] 的打印 。因为最后一次打印操作（将整个区间刷成 s[i] ）可以和打印左区间 [i, k] 或右区间 [k, j] 的某次操作合并。一个更直观的理解是：打印 [i, j] 的最少次数，不会超过打印 [i, j-1] 的最少次数。因为当我们要打印 [i, j] 时，可以先按打印 [i, j-1] 的方式操作，在最后一步，我们本可以只打印 j 这个位置，但因为我们允许一次打印一个区间，而 s[i] == s[j] ，所以我们可以在某次打印 s[i] 的时候，顺带把 j 这个位置也打印了。因此， dp[i][j] = dp[i][j-1] 。（同理， dp[i][j] = dp[i+1][j] ） 情况二 ：如果区间两端的字符不同，即 s[i] != s[j] 。那么我们就需要将区间 [i, j] 拆分成两个更小的子区间，分别打印。我们需要找到一个分割点 k （ i <= k < j ），使得总打印次数最少。即 dp[i][j] = min(dp[i][k] + dp[k+1][j]) ，其中 k 遍历从 i 到 j-1 的所有位置。 第二步：构建动态规划表 我们需要一个二维数组 dp ，其维度为 n x n （ n 是字符串 s 的长度）。由于我们依赖的是更短的区间，所以我们应该按照区间的长度 len 从小到大来遍历和计算 dp[i][j] 。 初始化 ：对于所有 i ， dp[i][i] = 1 。 循环遍历 ： 外层循环遍历区间长度 len ，从 2 到 n （因为长度为1的区间已经初始化好了）。 内层循环遍历区间的起始点 i ，从 0 到 n - len 。 计算区间的结束点 j = i + len - 1 。 状态转移 ： 如果 s[i] == s[j] ，则 dp[i][j] = dp[i][j-1] 。为什么不是 dp[i+1][j] ？其实两者都可以，因为它们都代表了“忽略一端已经正确的字符”的思想。我们选择其中一种即可，例如 dp[i][j-1] 。 如果 s[i] != s[j] ，则 dp[i][j] = min(dp[i][k] + dp[k+1][j]) ，其中 k 从 i 遍历到 j-1 。 第三步：举例说明 以 s = "aba" 为例， n = 3 。 初始化 ： dp[0][0] = 1 (打印 "a") dp[1][1] = 1 (打印 "b") dp[2][2] = 1 (打印 "a") 计算长度为2的区间 ： [0,1] ：s[ 0]='a', s[ 1 ]='b'，不同。 k=0 : dp[0][0] + dp[1][1] = 1 + 1 = 2 dp[0][1] = min(2) = 2 [1,2] ：s[ 1]='b', s[ 2 ]='a'，不同。 k=1 : dp[1][1] + dp[2][2] = 1 + 1 = 2 dp[1][2] = min(2) = 2 计算长度为3的区间 [0,2] ： s[ 0]='a', s[ 2 ]='a'，相同。 根据状态转移方程： dp[0][2] = dp[0][1] ？ 不对，这里应该是 dp[0][2] = dp[0][2-1] 也就是 dp[0][1] ？ 我们得到 dp[0][2] = 2 。 验证 ：如何用两次操作打印 "aba"？ 方案一：第一次打印整个区间 [0,2] 为 'a'，得到 "aaa"。第二次打印区间 [1,1] 为 'b'，覆盖掉中间的 'a'，得到 "aba"。总共2次。 方案二：第一次打印区间 [0,0] 为 'a'，第二次打印区间 [1,2] 为 'ba'（这是一次操作，因为一次操作可以打印一个连续的区间为同一个字符，所以这里打印的是 'b'，但区间是 [1,2] ，所以打印出来是 "bb"？不对，这样会得到 "abb"）。所以方案二不正确。正确的方案是方案一。 实际上，因为 s[0] == s[2] ，我们可以将区间拆分为 [0,1] 和 [2,2] ，但 [2,2] 已经包含在第一次整体打印 'a' 的操作里了。所以 dp[0][2] 等于 dp[0][1] 是合理的，因为打印完 [0,1] 后， [2,2] 可以顺带在第一次打印 [0,2] 为 'a' 时完成。但更准确的理解是：当两端字符相同时，我们可以在打印左区间 [i, j-1] 的某次操作中，顺带把 j 也打印了，所以次数可以等于 dp[i][j-1] 。 最终答案 整个字符串 s 对应的是区间 [0, n-1] ，所以最少的打印次数就是 dp[0][n-1] 。 总结 这个问题的核心在于处理区间两端字符是否相同。如果相同，则可以优化打印次数，避免不必要的分割；如果不同，则必须尝试所有可能的分割点，找到最优解。通过自底向上地填充动态规划表，我们能够高效地计算出最终结果。