题目描述
思路解析
一句话答案：LeetCode 115 不同的子序列：二维动态规划，dp[i][j] 记 s 前 i 个字符里等于 t 前 j 个字符的方案数。相等时「选它 + 不选它」两条路相加，不等只继承。时间 O(m×n)、空间可滚到 O(n)。
不同的子序列这道题到底在数什么
给字符串 s 和 t，要在 s 里按原先后顺序挑字符、拼出和 t 一样的串，问有多少种不同挑法。子序列（从原串挑若干字符、保持先后、可跳过）不要求连续，但顺序不能乱。题面 s="rabbbit"、t="rabbit" 答案 3，三种挑法只差在中间三个 b 挑哪两个。
把 s 的子序列全列出来为什么行不通
s 每个字符可挑可不挑，长 n 就有 2 的 n 次方个子序列，逐个和 t 比对便是天文数字。而且相同前缀的子序列被反复重拼、同一中间结果本该只算一次。把「s 前若干个字符能凑 t 前若干个字符」记下复用，指数级枚举就压成一张表逐格递推（用已算好的格子推出当前格）。
dp[i][j] 该定成什么，第 0 列为什么全填 1
这题用动态规划（把「s 前若干个字符能凑 t 前若干个字符有几种挑法」逐格存表、直接取不重算）。定义 dp[i][j]（i、j 从 0 数起，i 行 j 列）为「s 前 i 个字符里能凑出 t 前 j 个字符的挑法数」。铺边界：第 0 列 dp[i][0] 全是 1——凑空的 t 什么都不挑、唯一一种；第 0 行 dp[0][j]（j≥1）全是 0——s 空串凑不出非空 t。
字符相等时，为什么要把两条路相加
填 dp[i][j] 时只盯 s[i-1]（s 的第 i 个字符，下标从 0 数起）和 t[j-1]。两者不相等时，s 这个字符配不上 t 要的位、只能弃用，照搬正上方 dp[i-1][j]。
相等时有两条互不重叠的路、方案数相加。一条：用它当 t 的第 j 位，前面得用 s 前 i-1 个凑出 t 前 j-1 位，是左上角 dp[i-1][j-1]；另一条：不用它，仍靠 s 前 i-1 个凑完整的 t 前 j 位，是正上方 dp[i-1][j]。「用」和「不用」互不重叠、不会重复计数，所以 dp[i][j]=dp[i-1][j-1]+dp[i-1][j]。
拿 rabbbit 和 rabbit 亲手把表填出来
表是 8 行 7 列（s 长 7、t 长 6 各加边界行列）。第 0 列全 1、余下全 0。方案数靠三个 b 长起来：（前面 r 配 r、a 配 a 各只有 1 种，落到 dp[2][2]=1；dp[2][3]=0）dp[3][3]=dp[2][2]+dp[2][3]=1+0=1，dp[4][3]=dp[3][2]+dp[3][3]=1+1=2，dp[5][3]=dp[4][2]+dp[4][3]=1+2=3。收尾 dp[7][6]=dp[6][5]+dp[6][6]=3+0=3，正是用整个 rabbbit 凑出 rabbit 的总数，对上题面。
第 0 列少填一个 1，整张表为什么一路塌成 0
整张表 (m+1)×(n+1) 格，每格一次比较一次加法，时间 O(m×n)；填当前行只用得上正上方一行，把二维表压成一行就地覆盖（滚动数组），空间降到 O(n)。
最易写错的是第 0 列：漏填或错成 0，相等时「用这个字符」那条路接左上角就恒为 0、整张表塌成全 0，答案错成 0。第 0 行相反，s 空凑非空 t 必须是 0，误填 1 会多出挑法。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心就这一个表：行是 s 的前缀越来越长，列是要凑的 t 的前缀，每格存「到这里为止有几种凑法」。
先铺好第 0 列：不管 s 多长，要凑出「空的 t」永远只有 1 种办法——什么都不挑。第 0 行（s 空但 t 非空）则是 0 种。
当前 s 的 'r' 和要凑的 t 的 'r' 相等，有两条路：① 用它来当 t 的这位 → 看左上角 dp[0][0]=1 种；② 不用它、靠前面的 s 凑 → 看上方 dp[0][1]=0 种。两条路相加。
落子：dp[1][1] = 1 + 0 = 1。相等时「选用」与「不用」两种方案数相加。
当前 s 的 'r' 和要凑的 t 的 'a' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[0][2]=0 种。
落子：dp[1][2] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'r' 和要凑的 t 的 'b' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[0][3]=0 种。
落子：dp[1][3] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'r' 和要凑的 t 的 'b' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[0][4]=0 种。
落子：dp[1][4] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'r' 和要凑的 t 的 'i' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[0][5]=0 种。
落子：dp[1][5] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'r' 和要凑的 t 的 't' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[0][6]=0 种。
落子：dp[1][6] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'a' 和要凑的 t 的 'r' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[1][1]=1 种。
落子：dp[2][1] = 1（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'a' 和要凑的 t 的 'a' 相等，有两条路：① 用它来当 t 的这位 → 看左上角 dp[1][1]=1 种；② 不用它、靠前面的 s 凑 → 看上方 dp[1][2]=0 种。两条路相加。
落子：dp[2][2] = 1 + 0 = 1。相等时「选用」与「不用」两种方案数相加。
当前 s 的 'a' 和要凑的 t 的 'b' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[1][3]=0 种。
落子：dp[2][3] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'a' 和要凑的 t 的 'b' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[1][4]=0 种。
落子：dp[2][4] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'a' 和要凑的 t 的 'i' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[1][5]=0 种。
落子：dp[2][5] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'a' 和要凑的 t 的 't' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[1][6]=0 种。
落子：dp[2][6] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'b' 和要凑的 t 的 'r' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[2][1]=1 种。
落子：dp[3][1] = 1（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'b' 和要凑的 t 的 'a' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[2][2]=1 种。
落子：dp[3][2] = 1（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'b' 和要凑的 t 的 'b' 相等，有两条路：① 用它来当 t 的这位 → 看左上角 dp[2][2]=1 种；② 不用它、靠前面的 s 凑 → 看上方 dp[2][3]=0 种。两条路相加。
落子：dp[3][3] = 1 + 0 = 1。相等时「选用」与「不用」两种方案数相加。
当前 s 的 'b' 和要凑的 t 的 'b' 相等，有两条路：① 用它来当 t 的这位 → 看左上角 dp[2][3]=0 种；② 不用它、靠前面的 s 凑 → 看上方 dp[2][4]=0 种。两条路相加。
落子：dp[3][4] = 0 + 0 = 0。相等时「选用」与「不用」两种方案数相加。
当前 s 的 'b' 和要凑的 t 的 'i' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[2][5]=0 种。
落子：dp[3][5] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'b' 和要凑的 t 的 't' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[2][6]=0 种。
落子：dp[3][6] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'b' 和要凑的 t 的 'r' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[3][1]=1 种。
落子：dp[4][1] = 1（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'b' 和要凑的 t 的 'a' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[3][2]=1 种。
落子：dp[4][2] = 1（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'b' 和要凑的 t 的 'b' 相等，有两条路：① 用它来当 t 的这位 → 看左上角 dp[3][2]=1 种；② 不用它、靠前面的 s 凑 → 看上方 dp[3][3]=1 种。两条路相加。
落子：dp[4][3] = 1 + 1 = 2。相等时「选用」与「不用」两种方案数相加。
当前 s 的 'b' 和要凑的 t 的 'b' 相等，有两条路：① 用它来当 t 的这位 → 看左上角 dp[3][3]=1 种；② 不用它、靠前面的 s 凑 → 看上方 dp[3][4]=0 种。两条路相加。
落子：dp[4][4] = 1 + 0 = 1。相等时「选用」与「不用」两种方案数相加。
当前 s 的 'b' 和要凑的 t 的 'i' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[3][5]=0 种。
落子：dp[4][5] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'b' 和要凑的 t 的 't' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[3][6]=0 种。
落子：dp[4][6] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'b' 和要凑的 t 的 'r' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[4][1]=1 种。
落子：dp[5][1] = 1（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'b' 和要凑的 t 的 'a' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[4][2]=1 种。
落子：dp[5][2] = 1（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'b' 和要凑的 t 的 'b' 相等，有两条路：① 用它来当 t 的这位 → 看左上角 dp[4][2]=1 种；② 不用它、靠前面的 s 凑 → 看上方 dp[4][3]=2 种。两条路相加。
落子：dp[5][3] = 1 + 2 = 3。相等时「选用」与「不用」两种方案数相加。
当前 s 的 'b' 和要凑的 t 的 'b' 相等，有两条路：① 用它来当 t 的这位 → 看左上角 dp[4][3]=2 种；② 不用它、靠前面的 s 凑 → 看上方 dp[4][4]=1 种。两条路相加。
落子：dp[5][4] = 2 + 1 = 3。相等时「选用」与「不用」两种方案数相加。
当前 s 的 'b' 和要凑的 t 的 'i' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[4][5]=0 种。
落子：dp[5][5] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'b' 和要凑的 t 的 't' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[4][6]=0 种。
落子：dp[5][6] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'i' 和要凑的 t 的 'r' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[5][1]=1 种。
落子：dp[6][1] = 1（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'i' 和要凑的 t 的 'a' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[5][2]=1 种。
落子：dp[6][2] = 1（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'i' 和要凑的 t 的 'b' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[5][3]=3 种。
落子：dp[6][3] = 3（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'i' 和要凑的 t 的 'b' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[5][4]=3 种。
落子：dp[6][4] = 3（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 'i' 和要凑的 t 的 'i' 相等，有两条路：① 用它来当 t 的这位 → 看左上角 dp[5][4]=3 种；② 不用它、靠前面的 s 凑 → 看上方 dp[5][5]=0 种。两条路相加。
落子：dp[6][5] = 3 + 0 = 3。相等时「选用」与「不用」两种方案数相加。
当前 s 的 'i' 和要凑的 t 的 't' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[5][6]=0 种。
落子：dp[6][6] = 0（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 't' 和要凑的 t 的 'r' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[6][1]=1 种。
落子：dp[7][1] = 1（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 't' 和要凑的 t 的 'a' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[6][2]=1 种。
落子：dp[7][2] = 1（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 't' 和要凑的 t 的 'b' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[6][3]=3 种。
落子：dp[7][3] = 3（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 't' 和要凑的 t 的 'b' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[6][4]=3 种。
落子：dp[7][4] = 3（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 't' 和要凑的 t 的 'i' 不相等，这个字符没法用，只能「不用它」：直接照搬上方 dp[6][5]=3 种。
落子：dp[7][5] = 3（不等，方案数和上一行一样，没新增凑法）。
当前 s 的 't' 和要凑的 t 的 't' 相等，有两条路：① 用它来当 t 的这位 → 看左上角 dp[6][5]=3 种；② 不用它、靠前面的 s 凑 → 看上方 dp[6][6]=0 种。两条路相加。
落子：dp[7][6] = 3 + 0 = 3。相等时「选用」与「不用」两种方案数相加。
右下角 dp[7][6] = 3，就是用整个 "rabbbit" 凑出 "rabbit" 的不同方案总数。
边界先想清。
两个高频追问。
参考代码
def numDistinct(s, t): m, n = len(s), len(t) dp = [[0]*(n+1) for _ in range(m+1)] for r in range(m+1): dp[r][0] = 1 for r in range(1, m+1): for c in range(1, n+1): if s[r-1] == t[c-1]: dp[r][c] = dp[r-1][c-1] + dp[r-1][c] else: dp[r][c] = dp[r-1][c] return dp[m][n]复杂度
- 时间：O(m·n)，每格 O(1)，共 (m+1)×(n+1) 格
- 空间：O(m·n)，整表；每格只依赖上一行，可滚动到 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么不等时只看上方、不看左上？
追问能优化空间吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
编辑距离
LeetCode 72 · 困难 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题