大厂P8,跳槽去小厂当副总,3个月被开了~

这不，圈里最近又传出一桩：某大厂P8跳去创业公司当副总级别，结果三个月就被请走了

按爆料说，这哥们技术底子硬，带过三十来号人，扛过好几个亿级项目。创业公司刚融到B轮，开价也挺“香”：工资往上抬一截，再塞一把期权。入职那天老板还挺会整活，亲自群发邮件说技术路线以后听他拍板，排面拉满。

我觉得这种戏最扎心的地方在于：大厂看你是“体系里的一块砖”，小厂一开始把你捧成“方向盘”，可真到业务转弯、现金流紧、老板想法一变，方向盘就可能先被拆下来。

那天晚上加班到快十一点，脑子已经半糊涂了，产品突然甩给我一句：“你这个接口逻辑有点像那个…奇怪的打印机的题哦。”我当时一愣：打印机？我这不是在写接口，是在写简历难度嘛。

题目大概就是这样：有个古早的打印机，它一次只能打印一整段“同一个字符”的连续区间，比如一口气打出 aaaa，位置你随便选；而且可以在之前打印过的地方再覆盖。问你，给定一个字符串，最少打印几次能搞定。听着就挺抽象对吧。

我一开始脑子一热，想贪心：从左往右扫，看到新字符就打一下，结果随便一测 "aba" 就翻车了——你如果先整体打一遍 aaa，中间那个位置再覆盖成 b，两次就搞定，但从左往右憨憨地算就是 3 次。那一刻我就知道：完了，又是 DP 要出场了。

这个题的正确思路其实蛮优雅的，就是区间 DP。你可以这么想：我们关心的是子串 s[i..j] 最少要打几次，把它记成 dp[i][j]。一个字符的时候很好说，i == j 的时候，只要打一次：

publicintstrangePrinter(String s){if (s == null || s.isEmpty()) return0;// 先压缩一下，把连续重复的字符折叠掉，比如 "aaabbb" -> "ab"    String t = compress(s);int n = t.length();int[][] dp = newint[n][n];for (int i = 0; i < n; i++) {        dp[i][i] = 1;    }// 区间长度从 2 开始for (int len = 2; len <= n; len++) {for (int i = 0; i + len - 1 < n; i++) {int j = i + len - 1;// 先假设最后一位单独打一枪int best = dp[i][j - 1] + 1;// 尝试和前面的某个位置一起打for (int k = i; k < j; k++) {if (t.charAt(k) == t.charAt(j)) {// 如果 k 和 j 字符一样，可以和 j 这次合并打印int candidate = dp[i][k] + (k + 1 <= j - 1 ? dp[k + 1][j - 1] : 0);if (candidate < best) {                        best = candidate;                    }                }            }            dp[i][j] = best;        }    }return dp[0][n - 1];}

上面这坨代码别急着看晕，我口胡解释一下哈：dp[i][j] 有一个特别自然的“最笨解法”——先把前面 i..j-1 都打完，再单独打 j 这个字符，所以是 dp[i][j-1] + 1。但有时候我们可以“蹭打印”：如果在 i..j-1 里面有一个位置 k，它的字符和 j 一样，那我完全可以在打印 s[k] 那一次顺手把 j 这个位置也一起涂上，等于省了一次。

于是就有了这个合并逻辑：在所有 s[k] == s[j] 的 k 里，找一个最划算的拆法： 左边 i..k 打完是 dp[i][k] 次，中间 k+1..j-1 这块是被我们“拆开”的，需要单独打，是 dp[k+1][j-1] 次。最后 k 和 j 那一下我们当成同一次打印，这次就不用额外加 1 了。

压缩函数也挺简单，就是把连续重复的字符干掉，不影响答案，还能让 DP 快不少：

private String compress(String s){    StringBuilder sb = new StringBuilder();char prev = 0;for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (i == 0 || c != prev) {            sb.append(c);            prev = c;        }    }return sb.toString();}

为啥可以这么压？直觉上就是：连续的 aaaa，怎么分次打都可以合成一次“整体打印 a”的操作，中间没有别的字符插队，所以数量只跟“不同块”的个数有关，和一块里面有几个 a 没关系。

写完之后我顺手测了几个例子："aba" -> 2 次，"aaabbb" -> 2 次，"abcabc" 这种鬼东西算出来是 5 次，看着就知道这打印机挺费墨的。

有意思的是，这个 DP 思路我之前写 Postgres 和 MySQL 那篇性能对比的时候就有类似的感觉：你以为一个个 SQL 打出去就完事了，结果真正优化的时候，是要把“可以合并的操作”塞到一条语句里，少走几趟网络。 这个打印机题也是一样，本质就是：能合并的地方，一定要想办法合并，把“多次打印”凑成“一次顺手带上”。

总之，这题如果你第一次做，脑子里别老想着“我下一步要打印哪一段”，那条路十有八九跑到贪心里去了；换个角度，问自己一句：某个子串最少要打印几次？把这个问题搞定了，整串自然就出来了。

行了，我得去处理测试给我提的另一个 bug 了，比打印机还奇怪，等我哪天想明白了再来唠一局。