从大厂员工吐槽到LeetCode刷题：我用“区间DP”解“奇怪的打印机”

刷到一条帖子，一位大厂哥们吐槽自己人生很失败，说赚了一千多万，结果买房买在了高点，精准站岗；孩子成绩全班倒数；媳妇天天念叨，感觉家里像开了循环日志，报错不停。

评论区也挺真实。有网友安慰说：房子亏了就当成交学费，别把自己人也亏进去。

要我说，这种感觉就像系统里变量太多，线程还互相抢锁，不崩才怪。这种帖子我爱看，省得我以为只有自己在生活里踩坑。它的好处也简单：一边围观一边捡点经验，顺手把焦虑降降温，回头说不定能少走几步弯路。

面试题：奇怪的打印机

说起踩坑，最近正好看到一个挺有意思的面试题，叫“奇怪的打印机”。我一看到这题目，就想起公司那台老古董打印机，心情好打一页，心情不好打半行就卡住，比产品经理的需求还阴晴不定……

题目描述其实就一句话：有一台打印机，每次只能选择一种字符，并将这种字符打印到一段任意长度的连续区间上（新打印的可以覆盖之前打印的字符）。问最少需要打印多少次，才能打出给定的目标字符串。

听起来是不是有点绕？我刚看到的时候，第一反应是：这不就是贪心嘛，从左到右，一个连续相同的字符段算一次。结果自己一推演，马上发现不对。这感觉就像当初选数据库，在 MySQL 和 Postgres 之间纠结，以为简单对比下就行，结果细节多到头皮发麻。

你想象一下，目标字符串是 aba。如果按“连续段”的思路来：

• 先打 aaa（三个位置都是 a）。
• 再在中间那个位置覆盖打印一个 b。
  这样需要两次，看起来挺完美。

但这个例子恰恰暴露了问题的核心：后面打印的字符可以覆盖前面的。所以有时候“提前”多打一点，将来就能省下一次操作。这思路跟我们写代码时很像，比如写 SQL 查询顺手多拿两列数据，说不定后续别的功能就能直接复用，省得再查一次。

但凡看到这种“前后操作可以覆盖、可以合并”的问题，经验告诉我，基本就得考虑区间 DP 了。脑子里先构建一个二维数组 dp[i][j]，它表示打印出子串 s[i..j] 所需的最少次数。然后盯着这个区间琢磨：

• 最笨的方案：先把 s[i+1..j] 打完，然后再单独打一次 s[i]。所以我们可以得到一个初始值：dp[i][j] = dp[i+1][j] + 1。
• 聪明的合并：如果在区间 (i, j] 里存在一个位置 k，使得 s[k] == s[i]，那事情就有转机了。我们可以先把 s[i+1..k-1] 这个子串打完，然后一次性把字符 s[i]（也就是 s[k]）打印在从 i 到 k 的区间上，这样 i 和 k 就同时被搞定了。最后再处理剩下的 s[k..j] 部分。因此，状态转移方程可以是：dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j])。这里需要注意，当 k == i+1 时，dp[i+1][k-1] 表示一个空区间，次数为0。

光说不练假把式，直接上Java代码感受下节奏：

public class StrangePrinter {
    public int strangePrinter(String s) {
        if (s == null || s.length() == 0) return 0;
        // 关键优化：压缩连续相同字符，例如 "aaabbb" -> "ab"
        StringBuilder sb = new StringBuilder();
        char[] arr = s.toCharArray();
        sb.append(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != arr[i - 1]) {
                sb.append(arr[i]);
            }
        }
        char[] str = sb.toString().toCharArray();
        int n = str.length;
        int[][] dp = new int[n][n];

        // 长度为1的区间只需要打印一次
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // len 表示当前处理的区间长度
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                // 方案1：最笨的办法，单独打左端点字符
                dp[i][j] = dp[i + 1][j] + 1;
                // 方案2：尝试与后面相同的字符合并打印
                for (int k = i + 1; k <= j; k++) {
                    if (str[k] == str[i]) {
                        int left = (k == i + 1) ? 0 : dp[i + 1][k - 1];
                        dp[i][j] = Math.min(dp[i][j], left + dp[k][j]);
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
}

看这代码结构，双层循环再套一层，典型的“区间DP”模板脸，但仔细看里面有不少小心机：

1. 预处理压缩：先把连续相同的字符合并成一个。这一步千万别小看，它经常能把问题规模降下来，直接避免不必要的计算。这就好比线上服务压测前，先把调试日志关掉，减少无关干扰。
2. 初始化保证下限：dp[i][j] 先初始化为“单独打左端点”的方案，这保证了结果至少不会比最笨的方法更差。
3. 枚举合并点：然后遍历 k，去寻找“薅羊毛”的机会。只要 str[k] 和 str[i] 相同，就尝试能不能让它们共用一次打印，从而减少总次数。

有朋友一看三层循环就开始头大：“这时间复杂度能过吗？”冷静想想，经过连续字符压缩后，字符串的有效长度 n 通常不会太大。再说了，真实场景下连续相同字符很多，压缩效果往往比你想象的好。刷题的时候，这点复杂度真不算啥，总比线上写个全表扫描的SQL要强。

这道题理顺之后，你会发觉，以后再遇到这类“可覆盖、可合并”的操作问题，脑子里就应该自动浮现出一个区间DP的表格模型，然后一步步去填，而不是一上来就想用指针之类的方法硬搞。思路清晰，问题就解决了一半。

行，代码看完了，我也得去伺候一下办公室那台“真·奇怪打印机”了，它又卡纸了，解决它的难度可比这道算法题高多了。如果你也在刷题或者对技术生活有啥吐槽，欢迎来云栈社区聊聊，咱们一起少踩点坑。