不同的子序列——子序列计数DP的状态定义技巧
不同的子序列——子序列计数DP的状态定义技巧
适读人群：Java后端工程师、二维DP进阶学习者 | 阅读时长：约20分钟 | 难度：Hard
开篇故事
LeetCode 115"不同的子序列"，是一道非常考验状态定义能力的题。
第一次做这道题，我把它和LCS搞混了，以为是求公共子序列的数量。仔细读了几遍题目才明白：这道题问的是，在字符串 s 中，有多少个不同的子序列等于字符串 t？
这两道题的状态定义虽然类似，转移方程却截然不同。搞清楚它们的区别，能让你深刻理解"计数DP"和"最优化DP"在状态转移上的本质差异。
特别是在字符不匹配时的处理：LCS不匹配时取max，计数DP不匹配时怎么处理？这个细节是这道题的精髓。
一、题目解析
题号：LeetCode 115. Distinct Subsequences
题目描述：给你两个字符串 s 和 t，统计并返回在 s 的子序列中 t 出现的个数。
示例：
- 输入：s = "rabbbit"，t = "rabbit"，输出：3（可以删除3个'b'中的任意一个）
- 输入：s = "babgbag"，t = "bag"，输出：5
二、DP思路推导
2.1 状态定义
定义 dp[i][j] = s 的前 i 个字符中，包含 t 的前 j 个字符作为子序列的方案数
2.2 状态转移方程推导
关注 s[i-1] 和 t[j-1] 的关系：
情况一：s[i-1] != t[j-1]
当前 s 的最后一个字符不能用来匹配 t[j-1]。只能放弃 s[i-1]，在 s 的前 i-1 个字符中找 t 的前 j 个字符的子序列：
dp[i][j] = dp[i-1][j]情况二：s[i-1] == t[j-1]
当前字符匹配！有两种选择：
用 s[i-1] 来匹配 t[j-1]：在 s 的前 i-1 个字符中找 t 的前 j-1 个字符作为子序列，方案数为
dp[i-1][j-1]不用 s[i-1] 来匹配 t[j-1]：放弃这次匹配机会，方案数为
dp[i-1][j]
两种选择相加：
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]完整转移方程：
dp[i][j] = dp[i-1][j] if s[i-1] != t[j-1]
dp[i][j] = dp[i-1][j-1] + dp[i-1][j] if s[i-1] == t[j-1]关键点：字符相等时，不是取max，而是求和。因为我们在计数，"用这次机会"和"不用这次机会"是两条独立的路径，都要计入。
2.3 边界条件
dp[i][0] = 1：t 为空，空串是任意字符串的子序列，且只有1种方式（什么都不选）dp[0][j] = 0（j > 0）：s 为空，无法包含非空的 t
2.4 状态转移示意
s = "rabbbit", t = "rabbit"
"" r a b b i t
"" [ 1 0 0 0 0 0 0 ]
r [ 1 1 0 0 0 0 0 ]
a [ 1 1 1 0 0 0 0 ]
b [ 1 1 1 1 0 0 0 ]
b [ 1 1 1 2 1 0 0 ]
b [ 1 1 1 3 3 0 0 ]
i [ 1 1 1 3 3 3 0 ]
t [ 1 1 1 3 3 3 3 ]
dp[7][6] = 3 ✓三、解法一：基础二维DP
public class DistinctSubsequences {
/**
* 115. 不同的子序列 - 二维DP
* 时间复杂度：O(m * n)
* 空间复杂度：O(m * n)
*/
public int numDistinct(String s, String t) {
int m = s.length();
int n = t.length();
// dp[i][j] = s前i字符中，t前j字符作为子序列出现的次数
long[][] dp = new long[m + 1][n + 1]; // 用long防溢出
// 边界：t为空，方案数为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++) {
// 不使用s[i-1]：在s的前i-1个字符里找t的前j个字符
dp[i][j] = dp[i - 1][j];
// 使用s[i-1]（前提：字符相等）
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] += dp[i - 1][j - 1];
}
}
}
return (int) dp[m][n];
}
}Mermaid状态转移：
四、解法二：空间优化（一维滚动）
/**
* 115. 不同的子序列 - 空间压缩到O(n)
* 倒序遍历，防止本轮值被提前覆盖
*/
public int numDistinctOptimized(String s, String t) {
int m = s.length();
int n = t.length();
long[] dp = new long[n + 1];
dp[0] = 1; // t为空，1种方案
for (int i = 1; i <= m; i++) {
// 倒序：防止dp[j-1]被本轮提前更新
// 注意：这里是01背包式的倒序，因为dp[i][j]依赖dp[i-1][j-1]（不能重复用s[i-1]）
for (int j = n; j >= 1; j--) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[j] += dp[j - 1]; // dp[j]是dp[i-1][j]，dp[j-1]是dp[i-1][j-1]（倒序保证）
}
// 不相等时，dp[j]不变（保持dp[i-1][j]）
}
}
return (int) dp[n];
}为什么这里倒序？
dp[i][j] = dp[i-1][j] + dp[i-1][j-1]（字符相等时）
空间压缩后，在处理 i 时，dp[j] 代表 dp[i-1][j]。如果正序更新，dp[j-1] 可能已经是 dp[i][j-1]（本轮更新过），而我们需要的是 dp[i-1][j-1]。倒序遍历保证 dp[j-1] 还没有被本轮更新，仍然是 dp[i-1][j-1]。
这和01背包倒序的原理完全相同！
五、与LCS的对比
| LCS（1143） | 不同子序列（115） | |
|---|---|---|
| 目标 | 最长公共子序列长度 | s中含t的子序列方案数 |
| 字符相等 | dp[i-1][j-1]+1（取最长） | dp[i-1][j-1]+dp[i-1][j]（累加方案） |
| 字符不等 | max(dp[i-1][j], dp[i][j-1]) | dp[i-1][j]（只从一个方向） |
| 两者关系 | 最优化问题 | 计数问题 |
关键区别：字符不等时，LCS需要从上方和左方取最大值（因为不用s[i-1]或不用t[j-1]都可以继续找）。但115的计数问题，t必须完整匹配，所以不用s[i-1]（dp[i-1][j]）可以，但不能不用t[j-1]（dp[i][j-1]），否则就跳过了t的一个字符，语义不对。
六、举一反三
子序列计数类题目：
- LeetCode 940. 不同的子序列II：统计字符串中不同子序列的个数（包括空序列）
- LeetCode 1987. 不同国家的数目：子序列计数变体
- LeetCode 2369. 检查数组是否存在有效划分：也是计数DP
七、踩坑实录
坑一：整数溢出
s 和 t 的长度可能到1000，dp的值可能非常大（指数级）。LeetCode上这道题的数据范围内int够用，但建议用long以防万一，最后再转int返回。
坑二：字符不等时写成了max(dp[i-1][j], dp[i][j-1])
这是把LCS的转移直接套过来的错误。115里字符不等时只能用 dp[i-1][j]，不能用 dp[i][j-1]，因为t必须完全匹配，不能跳过t的字符。
坑三：空间优化时用了正序
一维优化时必须倒序，原因和01背包完全相同：正序会把 dp[i-1][j-1] 变成 dp[i][j-1]，导致重复计算。
八、总结
不同的子序列是子序列计数DP的代表题，核心区别在于：
- 计数问题：字符相等时，用和不用当前字符的方案数相加（+）
- 最优化问题：字符相等时，取当前匹配后的最优值（max或+1）
这个区别彻底搞清楚，二维DP的计数问题就打通了。