不小心撞到X为员工索赔误工费 7500，看到流水证明后瞬间震惊。。

前两天看到个热搜，一网友骑车不小心撞到某为员工，对方三天误工费7500。

7500？三天？平均一天2500？我算了下，这相当于我上班加班写需求写到凌晨、还要在微信群里随时待命的两周工资……还是税前的。😭

更绝的是，那位员工拿出了工资流水，白纸黑字，明明白白。不是讹你，是你确实撞上了“高价值员工”……你说我打拼十几年，升职加薪也算小有成绩，结果在误工费面前，啪一下就被按在地上摩擦，打工人和大厂人之间的天堑，真的一撞就显现了。

反正我现在看大马路上骑车的都小心多了，万一再撞到一个腾讯的，怕不是得卖房赔误工费。【备注:文末可领最新资料】

面试题：统计特殊子序列的数目

我记得上次刷到这题的时候是深夜三点，咖啡续不上了，脑子也当机了——“统计特殊子序列的数目”？看了半天题都快看出哲学感来了……不过别慌，咱这就拆开来说。

题目其实不算长，但有点“杀人诛心”。说的是一个由 0、1、2 组成的数组，找出里面有多少个形如 0 → 1 → 2 的子序列。注意哈，是子序列不是子串，也就是可以不连续，只要顺序对了就行。

听着是不是有点像以前写的三层嵌套 for 循环？是的，最暴力的做法确实是：

count = 0
n = len(nums)
for i in range(n):
if nums[i] == 0:
for j in range(i+1, n):
if nums[j] == 1:
for k in range(j+1, n):
if nums[k] == 2:
                        count += 1

看着清爽，运行崩溃😅，三层循环在大数据面前直接跪下。所以我们得换个思路，那就是动态规划，精髓来了，掏出我算法库里的常用三件套。

我们不妨维护三个变量：count0 表示出现过的 0 的个数，count01 表示 01 组合的个数，count012 表示 012 子序列的个数。

然后我们就一边扫描数组，一边更新：

• 遇到 0：说明我们又多了一个以 0 开头的可能；
• 遇到 1：可以接在之前所有的 0 后面，组成若干 01；
• 遇到 2：可以接在所有的 01 后面，组成合法的 012。

上代码：

defcount_special_subsequences(nums):
    mod = 10**9 + 7
    count0, count01, count012 = 0, 0, 0

for num in nums:
if num == 0:
            count0 = (2 * count0 + 1) % mod
elif num == 1:
            count01 = (2 * count01 + count0) % mod
elif num == 2:
            count012 = (2 * count012 + count01) % mod

return count012

是不是简洁多了？而且时间复杂度只有 O(n)，刷面试题的时候绝对是“秒杀型”选手。

这里 2 * countX + Y 这种写法其实有点技巧，为什么是乘 2 呢？因为每次遇到一个匹配数字的时候，你可以选择“要”或者“不要”，相当于把当前匹配状态的所有组合翻倍，然后加上新加入的路径。这种思路在刷类似“子序列计数”类题目时很常见，建议直接收录为模板题。

不过我当时第一次做的时候，脑子里没理清楚这逻辑，写成了三层 if，然后就开始疯狂打印调试变量——调了两个小时没调出来 😭。后来才知道这玩意其实是个典型的状态机模式：三个状态，状态转移靠当前输入更新前一个状态值。这不就是操作系统里教我们的状态机编程模式嘛。

哦对，别忘了最后的结果取模，leetcode 和面试都喜欢考这个细节，不取模直接错一半……真让人抓狂。

所以这题给我的最大教训就是，不要一看是子序列就脑抽写暴力，先想状态，再想转移，最后优化性能。也别嫌弃这种基础题，能刷明白了你再看“最长回文子序列”这类复杂 DP，就知道啥叫“打通任督二脉”了。