奇怪的打印机

字数 3283 2025-10-25 22:15:07

奇怪的打印机

题目描述
有一台奇怪的打印机，它每次打印时只能打印一段连续的相同字符。之后，它可以在已经打印的字符上继续打印，新打印的字符会覆盖掉原来对应位置上的字符。给定一个字符串 s，你的任务是计算出打印机打印出这个字符串所需的最少打印次数。

示例
输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa"，然后打印 "bbb" 覆盖掉后面的三个位置。

输入：s = "aba"
输出：2
解释：首先打印 "aaa"，然后在中间位置打印 'b' 覆盖掉第二个 'a'。或者先打印 "bbb"，然后在第一个位置打印 'a' 覆盖掉第一个 'b'。

解题思路
这个问题可以使用区间动态规划来解决。我们定义 dp[i][j] 表示打印出字符串 s 中从第 i 个字符到第 j 个字符的子串所需的最少打印次数。

步骤分解

基础情况
当子串长度为 1 时，即 i == j，只需要一次打印即可完成，所以 dp[i][i] = 1。
状态转移方程
对于更长的子串 s[i:j]，我们考虑两种情况：
- 情况一：如果 s[i] == s[j]，那么打印 s[i] 的时候可以顺便把 s[j] 也打印出来（因为打印机可以连续打印相同字符）。此时，我们可以在打印 s[i] 的基础上，考虑中间部分 s[i+1:j-1] 的打印次数。但更一般地，我们可以将问题转化为 dp[i][j] = dp[i][j-1]。为什么？因为当 s[i] == s[j] 时，我们可以在打印 s[i] 时一次性将整个区间打印成 s[i]，然后再处理中间的部分，但更优的策略是先将 s[i:j-1] 打印好，然后利用最后一次打印 s[i] 的机会覆盖到 s[j]，因此 dp[i][j] 至少不会超过 dp[i][j-1]。
- 情况二：如果 s[i] != s[j]，那么我们需要将子串分割成两部分，分别打印。我们尝试所有可能的分割点 k（i <= k < j），将子串分成 s[i:k] 和 s[k+1:j]，然后取所有分割方式中的最小值：

\[ dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] \} \]

但是，情况一还需要更细致的处理。实际上，当 s[i] == s[j] 时，我们并不总是直接等于 dp[i][j-1]，因为可能中间有更优的分割方式。更通用的状态转移方程是：

\[ dp[i][j] = \min(dp[i][j-1], \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] \}) \]

但当 s[i] == s[j] 时，我们可以进一步优化：因为第一次打印可以覆盖 i 和 j 位置，所以我们可以考虑 dp[i][j] = dp[i][j-1]（或者 dp[i+1][j]），但这样可能不是最优。实际上，更精确的做法是：如果 s[i] == s[j]，那么我们可以省去一次打印，因为我们可以利用打印 s[i] 的机会同时覆盖 j 位置。因此，我们可以将方程写为：

\[ dp[i][j] = \min(dp[i][j-1], dp[i+1][j]) \]

但这样仍然可能不够全面。最保险的方法是：无论 s[i] 是否等于 s[j]，我们都先尝试分割，然后如果 s[i] == s[j]，我们再多一种选择：dp[i+1][j] 或 dp[i][j-1]。但实际上，更常见的写法是：

\[ dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] \} \]

如果 s[i] == s[j]，那么我们可以用 dp[i][j-1] 来更新，因为打印 s[i] 时可以延伸到 j。

经过综合，常见的状态转移方程是：

初始化 dp[i][j] 为一个较大的数。
如果 s[i] == s[j]，则 dp[i][j] = dp[i][j-1]。
然后，对于所有 k 从 i 到 j-1，更新：

\[ dp[i][j] = \min(dp[i][j], dp[i][k] + dp[k+1][j]) \]

计算顺序
由于 dp[i][j] 依赖于更短的子串，我们需要按子串长度从小到大进行计算。即先计算所有长度为 1 的子串，然后长度为 2，依此类推，直到整个字符串。

示例推导
以 s = "aba" 为例：

初始化 dp 表：
```
  a b a
a 1 ? ?
b   1 ?
a     1
```
计算长度为 2 的子串：
- "ab"：s[0] != s[1]，dp[0][1] = min(dp[0][0] + dp[1][1]) = 1 + 1 = 2
- "ba"：同理，dp[1][2] = 2
计算长度为 3 的子串 "aba"：
- 因为 s[0] == s[2]，所以先设 dp[0][2] = dp[0][1] = 2？不对，这样会出错。正确做法是：
  - 尝试分割点 k=0：dp[0][0] + dp[1][2] = 1 + 2 = 3
  - 尝试分割点 k=1：dp[0][1] + dp[2][2] = 2 + 1 = 3
  - 但由于 s[0] == s[2]，我们可以用 dp[1][2] 来更新？不，更优的做法是：如果 s[i] == s[j]，那么我们可以先打印整个区间为 'a'，然后处理中间部分，即 dp[i+1][j-1] 次打印，但这里中间是 'b'，所以总次数为 1 + dp[i+1][j-1] = 1 + dp[1][1] = 1 + 1 = 2。
    因此，正确的状态转移方程应该是：

\[ dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] \} \]

 如果 `s[i] == s[j]`，则还可以用 `dp[i+1][j-1]` 来更新？不，更通用的写法是：

\[ dp[i][j] = \min(dp[i][j], dp[i+1][j], dp[i][j-1]) \]

 但这样可能会重复计算。实际上，最常见的正确写法是：

\[ dp[i][j] = \begin{cases} dp[i][j-1] & \text{if } s[i] == s[j] \\ \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] \} & \text{otherwise} \end{cases} \]

 但对于 `"aba"`，如果 `s[0] == s[2]`，则 `dp[0][2] = dp[0][1] = 2`？但这样会得到 2，正确。  
 验证：`"aba"` 最少需要 2 次打印，符合。

最终算法

初始化 dp 数组，dp[i][i] = 1。
对于长度 len 从 2 到 n：
- 对于起点 i 从 0 到 n-len：
  - 设 j = i + len - 1
  - 如果 s[i] == s[j]，则 dp[i][j] = dp[i][j-1]
  - 否则，dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] \}
返回 dp[0][n-1]。

复杂度分析

时间复杂度：O(n³)，因为有三层循环（长度、起点、分割点）。
空间复杂度：O(n²)，用于存储 dp 表。

这样，我们就得到了打印字符串所需的最少次数。

奇怪的打印机题目描述有一台奇怪的打印机，它每次打印时只能打印一段连续的相同字符。之后，它可以在已经打印的字符上继续打印，新打印的字符会覆盖掉原来对应位置上的字符。给定一个字符串 s ，你的任务是计算出打印机打印出这个字符串所需的最少打印次数。示例输入： s = "aaabbb" 输出： 2 解释：首先打印 "aaa" ，然后打印 "bbb" 覆盖掉后面的三个位置。输入： s = "aba" 输出： 2 解释：首先打印 "aaa" ，然后在中间位置打印 'b' 覆盖掉第二个 'a' 。或者先打印 "bbb" ，然后在第一个位置打印 'a' 覆盖掉第一个 'b' 。解题思路这个问题可以使用区间动态规划来解决。我们定义 dp[i][j] 表示打印出字符串 s 中从第 i 个字符到第 j 个字符的子串所需的最少打印次数。步骤分解基础情况当子串长度为 1 时，即 i == j ，只需要一次打印即可完成，所以 dp[i][i] = 1 。状态转移方程对于更长的子串 s[i:j] ，我们考虑两种情况：情况一：如果 s[i] == s[j] ，那么打印 s[i] 的时候可以顺便把 s[j] 也打印出来（因为打印机可以连续打印相同字符）。此时，我们可以在打印 s[i] 的基础上，考虑中间部分 s[i+1:j-1] 的打印次数。但更一般地，我们可以将问题转化为 dp[i][j] = dp[i][j-1] 。为什么？因为当 s[i] == s[j] 时，我们可以在打印 s[i] 时一次性将整个区间打印成 s[i] ，然后再处理中间的部分，但更优的策略是先将 s[i:j-1] 打印好，然后利用最后一次打印 s[i] 的机会覆盖到 s[j] ，因此 dp[i][j] 至少不会超过 dp[i][j-1] 。情况二：如果 s[i] != s[j] ，那么我们需要将子串分割成两部分，分别打印。我们尝试所有可能的分割点 k （ i <= k < j ），将子串分成 s[i:k] 和 s[k+1:j] ，然后取所有分割方式中的最小值： \[ dp[ i][ j] = \min_ {i \le k < j} \{ dp[ i][ k] + dp[ k+1][ j ] \} \] 但是，情况一还需要更细致的处理。实际上，当 s[i] == s[j] 时，我们并不总是直接等于 dp[i][j-1] ，因为可能中间有更优的分割方式。更通用的状态转移方程是： \[ dp[ i][ j] = \min(dp[ i][ j-1], \min_ {i \le k < j} \{ dp[ i][ k] + dp[ k+1][ j ] \}) \] 但当 s[i] == s[j] 时，我们可以进一步优化：因为第一次打印可以覆盖 i 和 j 位置，所以我们可以考虑 dp[i][j] = dp[i][j-1] （或者 dp[i+1][j] ），但这样可能不是最优。实际上，更精确的做法是：如果 s[i] == s[j] ，那么我们可以省去一次打印，因为我们可以利用打印 s[i] 的机会同时覆盖 j 位置。因此，我们可以将方程写为： \[ dp[ i][ j] = \min(dp[ i][ j-1], dp[ i+1][ j ]) \] 但这样仍然可能不够全面。最保险的方法是：无论 s[i] 是否等于 s[j] ，我们都先尝试分割，然后如果 s[i] == s[j] ，我们再多一种选择： dp[i+1][j] 或 dp[i][j-1] 。但实际上，更常见的写法是： \[ dp[ i][ j] = \min_ {i \le k < j} \{ dp[ i][ k] + dp[ k+1][ j ] \} \] 如果 s[i] == s[j] ，那么我们可以用 dp[i][j-1] 来更新，因为打印 s[i] 时可以延伸到 j 。经过综合，常见的状态转移方程是：初始化 dp[i][j] 为一个较大的数。如果 s[i] == s[j] ，则 dp[i][j] = dp[i][j-1] 。然后，对于所有 k 从 i 到 j-1 ，更新： \[ dp[ i][ j] = \min(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j ]) \] 计算顺序由于 dp[i][j] 依赖于更短的子串，我们需要按子串长度从小到大进行计算。即先计算所有长度为 1 的子串，然后长度为 2，依此类推，直到整个字符串。示例推导以 s = "aba" 为例：初始化 dp 表：计算长度为 2 的子串： "ab" ： s[0] != s[1] ， dp[0][1] = min(dp[0][0] + dp[1][1]) = 1 + 1 = 2 "ba" ：同理， dp[1][2] = 2 计算长度为 3 的子串 "aba" ：因为 s[0] == s[2] ，所以先设 dp[0][2] = dp[0][1] = 2 ？不对，这样会出错。正确做法是：尝试分割点 k=0 ： dp[0][0] + dp[1][2] = 1 + 2 = 3 尝试分割点 k=1 ： dp[0][1] + dp[2][2] = 2 + 1 = 3 但由于 s[0] == s[2] ，我们可以用 dp[1][2] 来更新？不，更优的做法是：如果 s[i] == s[j] ，那么我们可以先打印整个区间为 'a' ，然后处理中间部分，即 dp[i+1][j-1] 次打印，但这里中间是 'b' ，所以总次数为 1 + dp[i+1][j-1] = 1 + dp[1][1] = 1 + 1 = 2 。因此，正确的状态转移方程应该是： \[ dp[ i][ j] = \min_ {i \le k < j} \{ dp[ i][ k] + dp[ k+1][ j ] \} \] 如果 s[i] == s[j] ，则还可以用 dp[i+1][j-1] 来更新？不，更通用的写法是： \[ dp[ i][ j] = \min(dp[ i][ j], dp[ i+1][ j], dp[ i][ j-1 ]) \] 但这样可能会重复计算。实际上，最常见的正确写法是： \[ dp[ i][ j ] = \begin{cases} dp[ i][ j-1] & \text{if } s[ i] == s[ j ] \\ \min_ {i \le k < j} \{ dp[ i][ k] + dp[ k+1][ j ] \} & \text{otherwise} \end{cases} \] 但对于 "aba" ，如果 s[0] == s[2] ，则 dp[0][2] = dp[0][1] = 2 ？但这样会得到 2，正确。验证： "aba" 最少需要 2 次打印，符合。最终算法初始化 dp 数组， dp[i][i] = 1 。对于长度 len 从 2 到 n ：对于起点 i 从 0 到 n-len ：设 j = i + len - 1 如果 s[i] == s[j] ，则 dp[i][j] = dp[i][j-1] 否则， dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] \} 返回 dp[0][n-1] 。复杂度分析时间复杂度：O(n³)，因为有三层循环（长度、起点、分割点）。空间复杂度：O(n²)，用于存储 dp 表。这样，我们就得到了打印字符串所需的最少次数。