那天晚上加班到快十二点，准备关电脑溜了，一个小伙子突然在工位后面冒出来，说东哥东哥，有个“奇怪的打印机”你帮我看下。 我当时脑子一抽，以为是工位旁边那台打印机又卡纸了，结果一听，是道算法题，瞬间精神了半格。
大概意思你应该知道，就是有个打印机挺轴的，它一次只能选一段连续区间，把这一段全打成同一个字符，而且这一段可以覆盖之前已经打印过的内容，相当于“涂改液模式”。问你最少要打几次，才能把一串字符串打出来。听起来有点抽象对吧，其实特别像我们写 PPT，反复选中一大段，全换成红色，再选中中间一段换成蓝色，那种操作。
我第一眼当然也想暴力嘛，左边打一段，右边打一段，中间再瞎折腾一下。直觉告诉我，这玩意儿肯定是区间 DP，毕竟那种“从 i 到 j 最优”的味道一闻就有。只是当时脑子有点糊，差点把状态转移写成屎山。
你先想象一下，我们搞个 dp[i][j]，表示把子串 s[i…j] 打出来，最少要几次。最蠢的想法是：我先把 s[i] 单独打一遍，然后剩下 i+1…j 再搞，所以有一个很直接的式子：
dp[i][j] = dp[i + 1][j] + 1
意思就是：第一个字符自己先打一趟，再看后面怎么打。 但这样肯定不是最优的，比如字符串是 "aba"，如果你先打 'a'，再打 "ba"，你可能会多干活。
神奇的点在于：如果后面某个位置 k 上，s[k] 跟 s[i] 是一样的，那这两个位置其实可以“顺便一起打”。就像你打印文档时，发现前后两个地方都要变成红色，你不会分两次选区，对吧，你会一次选大点的区间顺手搞定。
所以当 s[i] == s[k] 的时候，你可以考虑这样分：
- 然后在 k…j 这段打的时候，顺便把 i 这个位置也覆盖成同样的字符
于是有了另一个状态转移： dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j])
听起来有点绕？你可以粗暴地理解成： “我把 i 这一格的贡献挪到了 k 那一趟里，少了一次单独打印”。
我当时就拿白板乱画，嘴里还念叨着： “反正就是这个…怎么说…i 跟后面的同色一起打就行了…你先相信我……”
还有个小细节，语音识别一下就可能识别错： 像 "aaabbb" 这种连续相同字符，打印机一次就能搞定，你如果在状态里还当成三个 'a' 分开处理，纯属浪费算力，所以一般会先把字符串压缩一下，把连续相同的字符缩成一个。这个优化不做，题也能过，就是会慢一点。
我给那同学写了个 Python 版本，大概长这样：
defstrange_printer(s: str) -> int:ifnot s:return0# 压缩一下连续相同字符，比如 "aaab" -> "ab" t = []for ch in s:ifnot t or t[-1] != ch: t.append(ch) s = ''.join(t) n = len(s) dp = [[0] * n for _ in range(n)]# 区间 DP，i 从右往左枚举for i in range(n - 1, -1, -1): dp[i][i] = 1# 单个字符，一次就够for j in range(i + 1, n):# 先假设把 s[i] 单独打一遍 dp[i][j] = dp[i + 1][j] + 1# 再尝试和后面相同字符合并打印for k in range(i + 1, j + 1):if s[k] == s[i]:# i 这一位挪到 k 那一轮一起打 cost = dp[i + 1][k - 1] + dp[k][j]if cost < dp[i][j]: dp[i][j] = costreturn dp[0][n - 1]
写完我习惯性跑个简单例子，"aba"，脑袋里过一遍过程：
- i=j 时，dp[0][0] = 1, dp[1][1] = 1, dp[2][2] = 1
- 对区间 [0,1]，"ab"：要么先打 'a' 再打 'b' → 2
- 最后 [0,2]，"aba"： 先按蠢办法：dp[1][2] + 1 = 3 但发现 s[0] == s[2]，可以让 0 和 2 一起打： 中间 [1,1] = 1，然后 dp[2][2] = 1，加起来 1 + 1 = 2 所以 dp[0][2] = 2，挺合理，一次打成 "aaa"，一次覆盖中间变 "b"。
当时那小伙子在旁边一直嗯嗯嗯，结果等我写完他来一句：“东哥，这是不是那个区间 DP 经典题啊，我刷题的时候跳过去了…” 我：你这不是跳过去，是跳到我头上来了。
这个题其实挺有代表性的： 看上去是打印机，实质是“区间 + 覆盖 + 选择顺序影响成本”。以后你再碰到那种“子串 [i…j] 最小/最大什么”的题，脑子里就可以先冒出一个 dp[i][j] 试试看，八成跑不了。
行了我先去泡个咖啡，等会儿估计又有人来问我为啥时间复杂度是 n 的三次方…
