京公网安备11010502063487号给定字符串 s 和 t，求 s 的子序列中等于 t 的不同方案数。标准做法是二维 DP，转移方程本身不难写对，但边界条件 dp[i][0]（用 s 的任意前缀匹配空目标串）必须初始化成 1，这一步极容易被漏掉。本文用真实反例证明：只要这个边界漏了，整张 DP 表就必然算出 0（不是偶尔出错，而是 100% 出错），并用 2000 组随机测试验证这个规律，再给出正确写法、5 种语言实现，以及 DP 表填表过程的分步演示。
本文只用自己的话概括题意，完整约束以官方页面为准。给定字符串 s 和 t，求 s 的子序列中等于 t 的不同方案数（子序列不要求连续，但要求方案计数——即使子序列的内容相同，只要是从 s 里删除了不同位置的字符得到的，也算不同的方案）。一共 5 组用例，覆盖：官方两个示例、空串对空串、非空对空串、完全不匹配：
s="rabbbit" t="rabbit" → 3 s="babgbag" t="bag" → 5 s="" t="" → 1 s="abc" t="" → 1 s="a" t="b" → 0
标准做法是二维 DP：dp[i][j] 表示用 s 的前 i 个字符能匹配出 t 的前 j 个字符的方案数。转移方程本身不难写对，但边界条件极容易漏掉一半：dp[i][0]（用 s 的任意前缀匹配"空目标串"）必须初始化成 1，因为"把 s 的这一段全部删空"本身就是恰好一种合法方案。如果这一步初始化被漏掉、保持默认的 0，那么所有依赖它的后续状态都会跟着算错：
s="rabbbit" t="rabbit"（官方示例，正确答案是3）\n正确写法（dp[i][0]=1） → 3\n陷阱写法（dp[i][0]默认为0） → 0
陷阱写法在这道题上不是"偶尔算错"，而是"必然算出 0"：因为整个二维表里唯一的非零起点就是这一行边界，一旦它全是 0，后续所有格子的递推全部建立在 0 的基础上，永远不可能凭空变出非零值。用 2,000 组随机 (s, t) 验证：
2,000 组随机 (s, t)，其中正确答案大于 0 的有 1,075 组；\n这些组里陷阱写法算出 0 的有 1,075 组，占 100.0%
只要正确答案本该是正数，陷阱写法就一定会算出 0——这是这道题边界条件的特殊之处：它不是"影响个别情况"的小 bug，而是整个 DP 表赖以启动的唯一起点。
dp[i][j]：用 s 的前 i 个字符匹配 t 的前 j 个字符的方案数。边界 dp[i][0] = 1（匹配空串只有一种方式：全删掉）。转移时，不管 s[i-1] 和 t[j-1] 是否相等，都可以选择不用 s[i-1]（继承 dp[i-1][j]）；如果两个字符相等，还可以额外选择用 s[i-1] 去匹配 t[j-1]（加上 dp[i-1][j-1]）。时间 O(mn)，空间 O(mn)。Python、Java、Go、JavaScript、C++ 都是真实编译运行的，用同一组 5 个测试用例。
Python · 解法代码def num_distinct(s, t): m, n = len(s), len(t) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = 1 # 空目标串：任何前缀都恰好有一种"全部不选"的匹配方式 for i in range(1, m + 1): for j in range(1, n + 1): dp[i][j] = dp[i - 1][j] # 不用 s[i-1] 去匹配 t[j-1] if s[i - 1] == t[j - 1]: dp[i][j] += dp[i - 1][j - 1] # 用 s[i-1] 去匹配 t[j-1] return dp[m][n]
$ python3 solution.py s="rabbbit" t="rabbit" → 3 s="babgbag" t="bag" → 5 s="" t="" → 1 s="abc" t="" → 1 s="a" t="b" → 0
Java · 解法代码class Solution { public int numDistinct(String s, String t) { int m = s.length(), n = t.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 0; i <= m; i++) dp[i][0] = 1; // 空目标串：任何前缀都恰好有一种匹配方式 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = dp[i - 1][j]; // 不用 s[i-1] 去匹配 t[j-1] if (s.charAt(i - 1) == t.charAt(j - 1)) { dp[i][j] += dp[i - 1][j - 1]; // 用 s[i-1] 去匹配 t[j-1] } } } return dp[m][n]; } }
$ javac -d build Main.java && java -cp build Main s="rabbbit" t="rabbit" → 3 s="babgbag" t="bag" → 5 s="" t="" → 1 s="abc" t="" → 1 s="a" t="b" → 0
Go · 解法代码func numDistinct(s string, t string) int { m, n := len(s), len(t) dp := make([][]int, m+1) for i := range dp { dp[i] = make([]int, n+1) dp[i][0] = 1 // 空目标串：任何前缀都恰好有一种匹配方式 } for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { dp[i][j] = dp[i-1][j] // 不用 s[i-1] 去匹配 t[j-1] if s[i-1] == t[j-1] { dp[i][j] += dp[i-1][j-1] // 用 s[i-1] 去匹配 t[j-1] } } } return dp[m][n] }
$ go run solution.go s="rabbbit" t="rabbit" → 3 s="babgbag" t="bag" → 5 s="" t="" → 1 s="abc" t="" → 1 s="a" t="b" → 0
JavaScript · 解法代码function numDistinct(s, t) { const m = s.length, n = t.length; const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0)); for (let i = 0; i <= m; i++) dp[i][0] = 1; // 空目标串：任何前缀都恰好有一种匹配方式 for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { dp[i][j] = dp[i - 1][j]; // 不用 s[i-1] 去匹配 t[j-1] if (s[i - 1] === t[j - 1]) { dp[i][j] += dp[i - 1][j - 1]; // 用 s[i-1] 去匹配 t[j-1] } } } return dp[m][n]; }
$ node run.js s="rabbbit" t="rabbit" → 3 s="babgbag" t="bag" → 5 s="" t="" → 1 s="abc" t="" → 1 s="a" t="b" → 0
C++ · 解法代码int numDistinct(string s, string t) { int m = s.size(), n = t.size(); vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0)); for (int i = 0; i <= m; i++) dp[i][0] = 1; // 空目标串：任何前缀都恰好有一种匹配方式 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = dp[i-1][j]; // 不用 s[i-1] 去匹配 t[j-1] if (s[i-1] == t[j-1]) { dp[i][j] += dp[i-1][j-1]; // 用 s[i-1] 去匹配 t[j-1] } } } return (int)dp[m][n]; }
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin s="rabbbit" t="rabbit" → 3 s="babgbag" t="bag" → 5 s="" t="" → 1 s="abc" t="" → 1 s="a" t="b" → 0
共 5 组用例（含边界），以 Python 结果为基准逐组比对：\n Python 通过 5/5\n Java 通过 5/5\n Go 通过 5/5\n JavaScript 通过 5/5\n C++ 通过 5/5
Python 版本的二维 DP 实现另外和一个独立写的自顶向下递归 + 记忆化版本做了随机对拍：dfs(i, j) 表示从 s 的第 i 个字符、t 的第 j 个字符开始还有多少种匹配方式，递归到 j == len(t) 时返回 1（天然对应"空目标串"这个边界，不容易漏掉）。
随机对拍 3,000 组（s 长度 0-12，t 长度 0-6，字符取 a/b/c），2D DP 版与自顶向下记忆化版的结果全部一致，0 处不一致。
另外四种语言只在上面 5 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用一个更小的例子 s="bbb"、t="bb"（正确答案是 3，对应从 3 个 b 里删掉任意 1 个的 3 种方式）：先填好边界（第一列全是 1），再逐行按转移方程填表，字符相等时要额外加上左上角的值。蓝色是正在计算的格子，绿色是已经算好的格子。每一帧都是把上面的解法在这组输入上真实执行记录下来的。