不同的子序列

枚举所有子序列是指数级。

dp[i][j] 表示 s 前 i 个组成 t 前 j 个的方案数；相等时可选也可不选。

定义状态 + 填好边界(第0行/第0列)：先把边界填好:第 0 列全 1(t 是空串,1 种拼法),第 0 行除角落全 0(s 是空串,拼不出非空 t)。

逐行填 · 每格看『s 当前字符 vs t 当前字符』：一行一行填:行 i 对应 s 的第 i 个字符。看 dp[3][3]——行3=s[2]='b'、列3=t[2]='b',相等,后面这种相等格要走『选/不选』两路相加。(动画画的是完整二维表帮理解;代码里用一维 dp[] 滚动复用每一行省内存,递推一模一样。)

相等分支:dp[4][3] = 上 + 左上：dp[4][3]:行4=s[3]='b'、列3=t[2]='b' 相等。两条路相加:不选这个 b(继承上面 dp[3][3]=1)+ 用这个 b 配掉 t 的 b(左上 dp[3][2]=1)= 2。

不等分支:dp[6][4] = 只继承上一行：dp[6][4]:行6=s[5]='i'、列4=t[3]='b' 不等。当前字符配不上,只能不选它,直接继承上一行 dp[5][4]=3。

右下角就是答案：填到右下角 dp[7][6]=3:rabbbit 里抠出 rabbit 有 3 种方式——三个 b 任选一个去配 t 里的那个 b。

一句话记住：dp[i][j] 表示 s 前 i 个组成 t 前 j 个的方案数；相等时可选也可不选。

边界三连：边界三连先过：空输入、单元素、重复或相等值。能过这三类，主逻辑才算站稳。

为什么是 3 · 三个 b 各一条路：核心:暴力枚举所有子序列是指数级;DP 把『每个前缀配每个前缀』的方案数存进 m×n 的表,每格 O(1) 推出,整体 O(m·n)。三个 b 的贡献沿 b 列累加成最终的 3。

面试追问 1：dp[i][j] 表示 s 前 i 个组成 t 前 j 个的方案数；相等时可选也可不选。

面试追问 2：面试追复杂度时，不要只报 O，要把“每个元素进出几次”讲清楚。

面试追问 3：不同的子序列 不是孤题，它练的是 二维动态规划 的状态设计。

这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=dp 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。