664. 奇怪的打印机

发表于 分类于 阅读次数： Waline： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

  • 区间DP

思路

1. 问题模型

给定字符串 \(s\)，长度为 \(n\)。打印机的一次操作可以：

  • 选择一个连续区间 \([L, R]\)
  • 选择一个字符 \(c\)
  • 将区间 \([L, R]\) 内的所有位置打印为 \(c\)
  • 允许覆写（后续操作可以覆盖之前的字符）

目标是：用最少的操作次数，打印出目标字符串 \(s\)。

由于允许覆写，打印顺序并不要求“一步到位”，可以先覆盖一大片，再逐步修正局部，这正是本题区间 DP 成立的根本原因。

2. 状态定义（1-index）

定义区间 DP： \[ f[i][j] = \text{打印出子串 } s[i..j] \text{ 的最少操作次数} \qquad (1 \le i \le j \le n) \] 边界条件：

  • 单字符区间： \[ f[i][i] = 1 \]

  • 空区间（用于统一转移）： \[ f[i][j] = 0 \quad \text{当 } i > j \]

最终答案为 \(f[1][n]\)。

3. 建模核心思想：右端点定稿

对于任意区间 \([i, j]\)，在任何合法打印方案中：

  • 位置 \(j\) 最终必须被打印成字符 \(s[j]\)
  • 必然存在一次操作打印字符 \(s[j]\) 并覆盖到位置 \(j\)
  • 且这是最后一次影响位置 \(j\) 的操作

因此，可以围绕“哪一次操作负责最终打印位置 \(j\)”来构造状态转移。

4. 基础转移：位置 \(j\) 单独打印

最保守、一定可行的方案是：

  1. 先打印左侧区间 \([i, j-1]\)，代价为 \(f[i][j-1]\)
  2. 再单独对位置 \(j\) 打印一次字符 \(s[j]\)

文本图（等宽对齐）：

1
2
3
索引:   i .......... j-1 | j
区间:  [  s[i..j-1]     ] [j]
操作:      先完成左段     +1 次打印

因此有： \[ f[i][j] \le f[i][j-1] + 1 \] 在实现中，通常将其作为初始值。

5. 合并打印：利用同字符位置 \(k\)

若存在某个位置 \(k\) 满足： \[ i \le k \le j-1 \quad \text{且} \quad s[k] = s[j] \] 则可以尝试将“打印 \(s[j]\) 的那一笔”与“打印 \(s[k]\) 的某一笔”合并，从而减少操作次数。

在本解法中，同时考虑两种合法的合并方式。

6. 合并方式一：从左段合并（\(f[i][k] + f[k+1][j-1]\)）

区间结构

1
2
索引:   i .......... k | k+1 .......... j-1 | j
区间:  [   s[i..k]     ] [   s[k+1..j-1]   ] [j]

构造思路

  1. 用 \(f[i][k]\) 次操作打印出左段 \([i, k]\)
    • 在这些操作中，必然存在一次打印字符 \(s[k]=s[j]\) 并覆盖位置 \(k\)
  2. 将该次操作的区间向右扩展到 \(j\)
    • 这样位置 \(j\) 会被同一笔打印为 \(s[j]\)
    • 中间区间 \([k+1, j-1]\) 可能被暂时刷成错误字符
  3. 再用 \(f[k+1][j-1]\) 次操作修复中间区间

得到合法上界： \[ f[i][j] \le f[i][k] + f[k+1][j-1] \]

7. 合并方式二：从右段合并（\(f[i][k-1] + f[k][j-1]\)）

区间结构

1
2
索引:   i .......... k-1 | k .......... j-1 | j
区间:  [   s[i..k-1]     ] [   s[k..j-1]     ] [j]

构造思路

  1. 用 \(f[i][k-1]\) 次操作完成左段 \([i, k-1]\)
  2. 用 \(f[k][j-1]\) 次操作完成右段 \([k, j-1]\)
    • 在这组操作中，必然存在一次打印字符 \(s[k]=s[j]\) 并覆盖位置 \(k\)
  3. 将这一次操作的区间向右扩展到 \(j\)
    • 该扩展不会破坏 \([k, j-1]\) 的最终结果
    • 同时把位置 \(j\) 正确打印为 \(s[j]\)

因此同样有： \[ f[i][j] \le f[i][k-1] + f[k][j-1] \]

8. 完整状态转移方程

综合基础情况与两种合并方式： \[ \boxed{ f[i][j] = \min\Bigg( f[i][j-1] + 1,\; \min_{\substack{k \in [i, j-1] \\ s[k] = s[j]}} \big( f[i][k] + f[k+1][j-1],\; f[i][k-1] + f[k][j-1] \big) \Bigg) } \] 其中空区间项按 \(f[x][y]=0\ (x>y)\) 处理。

9. 示例说明（aba）

字符串：aba（1-index）

1
2
索引:   1   2   3
字符:   a   b   a

计算 \(f[1][3]\)：

  • 基础：\(f[1][2] + 1 = 3\)
  • 取 \(k=1\)，且 \(s[1]=s[3]\)
    • 左合并：\(f[1][1] + f[2][2] = 2\)
    • 右合并：\(f[1][0] + f[1][2] = 2\)

最终 \(f[1][3] = 2\)。

10. 复杂度分析

  • 状态数：\(O(n^2)\)
  • 每个状态枚举 \(k\)：\(O(n)\)
  • 时间复杂度：\(O(n^3)\)
  • 空间复杂度：\(O(n^2)\)

11. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int strangePrinter(string s) {
        int f[105][105] = {}, n = s.size();

        // 单字符区间
        for (int i = 1; i <= n; ++i)
            f[i][i] = 1;

        // 枚举区间长度
        for (int len = 2; len <= n; ++len) {
            for (int j = len; j <= n; ++j) {
                int i = j - len + 1;
                int mi = f[i][j - 1] + 1;  // 基础情况

                for (int k = j - 1; k >= i; --k) {
                    if (s[k - 1] == s[j - 1]) {
                        mi = min(mi,
                                 min(f[i][k] + f[k + 1][j - 1],
                                     f[i][k - 1] + f[k][j - 1]));
                    }
                }
                f[i][j] = mi;
            }
        }
        return f[1][n];
    }
};