当前位置：首页 > news >正文

动态规划解LeetCode 115：不同子序列计数问题

news 2026/8/10 10:01:39

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)，是面试中最推荐的写法。