1. 问题背景与理解第一次看到LeetCode 115题不同的子序列时我盯着题目描述足足看了五分钟。这道题在动态规划分类中属于中等难度但它的解法思路却让很多初学者感到困惑。题目要求我们计算字符串s中有多少种不同的子序列等于字符串t这里的子序列指的是在不改变字符顺序的情况下通过删除某些字符得到的新字符串。举个例子如果s rabbbitt rabbit那么有3种方式可以从s中得到trabb b it 删除第二个bra b bbit 删除第三个brab b bit 删除第四个b这个例子生动展示了子序列问题的核心特征——顺序必须保持一致但允许跳过中间字符。理解这一点对解题至关重要。2. 暴力递归解法分析2.1 基础递归思路最直观的解法是使用递归。我们可以定义递归函数count(i,j)表示在s的前i个字符和t的前j个字符中t的前j个字符作为子序列出现在s的前i个字符中的次数。递归的终止条件有两种当j0时表示t已经匹配完成返回1当i0但j0时表示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 j0时空字符串无法包含非空子序列状态转移方程当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表格填充示例以srabbbittrabbit为例初始化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不为空返回0t为空返回1空字符串是任何字符串的子序列两者都为空返回15.2 大数溢出问题当结果很大时比如s和t都是相同的长字符串结果可能超过普通整型范围。在Python中这不是问题但在其他语言如C中需要考虑使用长整型。5.3 性能极限测试对于sa*1000ta*100的情况即使使用DP解法也需要处理较大的计算量。在实际编码中可以提前判断如果len(t) len(s)直接返回0如果t为空直接返回16. 类似题目与举一反三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序列比对在生物信息学中比较基因序列的相似性版本控制系统比较代码文件的变化拼写检查计算单词之间的相似度自然语言处理评估句子相似性理解子序列问题的解法可以帮助我们在这些领域设计更高效的算法。