1. 问题背景与理解
第一次看到LeetCode 115题"不同的子序列"时，我盯着题目描述足足看了五分钟。这道题在动态规划分类中属于中等难度，但它的解法思路却让很多初学者感到困惑。题目要求我们计算字符串s中有多少种不同的子序列等于字符串t，这里的子序列指的是在不改变字符顺序的情况下，通过删除某些字符得到的新字符串。
举个例子，如果s = "rabbbit"，t = "rabbit"，那么有3种方式可以从s中得到t：
- rabb b it （删除第二个b）
- ra b bbit （删除第三个b）
- rab b bit （删除第四个b）
这个例子生动展示了子序列问题的核心特征——顺序必须保持一致，但允许跳过中间字符。理解这一点对解题至关重要。
2. 暴力递归解法分析
2.1 基础递归思路
最直观的解法是使用递归。我们可以定义递归函数count(i,j)，表示在s的前i个字符和t的前j个字符中，t的前j个字符作为子序列出现在s的前i个字符中的次数。
递归的终止条件有两种：
- 当j=0时，表示t已经匹配完成，返回1
- 当i=0但j>0时，表示s已经用完但t还未匹配完，返回0
递归关系也有两种情况：
- 如果s[i-1] == t[j-1]，可以选择匹配这个字符，也可以选择不匹配
- 如果s[i-1] != t[j-1]，只能选择不匹配这个字符
这种递归解法虽然直观，但时间复杂度高达O(2^n)，在LeetCode上会超时。不过，理解这个基础解法对后续优化至关重要。
2.2 递归代码实现
def numDistinct(s: str, t: str) -> int: def helper(i, j): if j == 0: return 1 if i == 0: return 0 if s[i-1] == t[j-1]: return helper(i-1, j-1) + helper(i-1, j) else: return helper(i-1, j) return helper(len(s), len(t))这段代码清晰地展现了递归思路，但在实际运行中，对于较长的字符串（比如s长度100+），性能会急剧下降。
3. 动态规划解法优化
3.1 DP状态定义
为了优化时间复杂度，我们引入动态规划。定义dp[i][j]表示s的前i个字符中t的前j个字符作为子序列出现的次数。这个定义与递归解法中的count(i,j)完全对应。
初始化条件：
- dp[i][0] = 1 （空字符串是任何字符串的子序列）
- dp[0][j] = 0 （j>0时，空字符串无法包含非空子序列）
状态转移方程：
- 当s[i-1] == t[j-1]时：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
- 当s[i-1] != t[j-1]时：dp[i][j] = dp[i-1][j]
3.2 DP表格填充示例
以s="rabbbit"，t="rabbit"为例：
初始化dp表格大小为(8,7)（包含空字符串情况）
填充过程：
- 第一行（除dp[0][0]外）全为0
- 第一列全为1
- 逐步填充其余单元格
最终dp[7][6] = 3，与示例结果一致。
3.3 DP代码实现
def numDistinct(s: str, t: str) -> int: 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): if s[i-1] == t[j-1]: dp[i][j] = dp[i-1][j-1] + dp[i-1][j] else: dp[i][j] = dp[i-1][j] return dp[m][n]这个解法的时间复杂度为O(mn)，空间复杂度也是O(mn)，已经比递归解法高效很多。
4. 空间优化技巧
4.1 滚动数组优化
观察状态转移方程，我们发现dp[i][j]只依赖于上一行的数据。因此可以使用一维数组来优化空间复杂度：
def numDistinct(s: str, t: str) -> int: m, n = len(s), len(t) dp = [0] * (n + 1) dp[0] = 1 for i in range(1, m + 1): prev = dp.copy() for j in range(1, n + 1): if s[i-1] == t[j-1]: dp[j] = prev[j-1] + prev[j] else: dp[j] = prev[j] return dp[n]4.2 反向遍历优化
更巧妙的是，我们可以反向遍历j，这样就不需要额外的prev数组：
def numDistinct(s: str, t: str) -> int: m, n = len(s), len(t) dp = [0] * (n + 1) dp[0] = 1 for i in range(1, m + 1): for j in range(n, 0, -1): if s[i-1] == t[j-1]: dp[j] += dp[j-1] return dp[n]这种优化将空间复杂度降到了O(n)，是面试中最推荐的写法。
5. 边界条件与特殊测试用例
5.1 空字符串处理
- s为空，t不为空：返回0
- t为空：返回1（空字符串是任何字符串的子序列）
- 两者都为空：返回1
5.2 大数溢出问题
当结果很大时（比如s和t都是相同的长字符串），结果可能超过普通整型范围。在Python中这不是问题，但在其他语言如C++中需要考虑使用长整型。
5.3 性能极限测试
对于s="a"*1000，t="a"*100的情况，即使使用DP解法也需要处理较大的计算量。在实际编码中，可以提前判断：
- 如果len(t) > len(s)，直接返回0
- 如果t为空，直接返回1
6. 类似题目与举一反三
6.1 LeetCode 392. 判断子序列
这道简单题可以看作是本题的简化版，只需要判断是否存在子序列，而不需要计数。
6.2 LeetCode 72. 编辑距离
虽然题目不同，但状态定义和转移思路有相似之处，都是基于两个字符串的匹配。
6.3 LeetCode 1143. 最长公共子序列
LCS问题与子序列计数问题有异曲同工之妙，都是动态规划的经典应用。
7. 面试技巧与常见错误
7.1 面试官可能问的问题
- 为什么初始条件是dp[i][0]=1？
- 如何从递归解法推导出DP解法？
- 空间优化思路是什么？
- 如果字符串包含Unicode字符，解法需要修改吗？
7.2 常见错误点
- 混淆子序列和子串的概念
- 初始化条件设置错误
- 索引处理不当（字符串从0开始但dp表从1开始）
- 在大数情况下忘记考虑溢出
7.3 代码调试技巧
在实现DP解法时，可以：
- 先写出递归解法确保逻辑正确
- 打印出完整的DP表格验证中间结果
- 用小的测试用例手动计算核对
8. 实际应用场景
虽然这看起来是一道纯算法题，但子序列计数在实际中有重要应用：
- DNA序列比对：在生物信息学中，比较基因序列的相似性
- 版本控制系统：比较代码文件的变化
- 拼写检查：计算单词之间的相似度
- 自然语言处理：评估句子相似性
理解子序列问题的解法，可以帮助我们在这些领域设计更高效的算法。
