请求为不同子序列计数问题的递归代码添加记忆化（缓存）实现

我明白你的困扰——原来的递归写法因为传递实际的子串sub，不仅效率低下，还很难直接加记忆化缓存。其实我们可以换一种状态定义思路，用双指针来表示当前的匹配进度，这样就能轻松实现记忆化，把指数级复杂度降到多项式级别。

原代码的问题分析 #

原函数check通过传递sub、i、length来追踪匹配状态，但sub这个字符串作为缓存键既占空间又冗余，而且length本质上就是t已经匹配的长度（相当于j指针）。我们完全不需要保存sub，只需要知道：当前处理到s的第i位，已经匹配到t的第j位，这样的状态对应的子序列数量就足够了。

带记忆化的递归解法（自顶向下DP） #

这里用Python的functools.lru_cache来实现记忆化，把i和j作为缓存的键：

from functools import lru_cache

def numDistinct(self, s: str, t: str) -> int:
    n = len(s)
    m = len(t)
    if n < m:
        return 0
    
    @lru_cache(maxsize=None)
    def dp(i, j):
        # 基准情况1：已经完全匹配t的所有字符，找到1个有效子序列
        if j == m:
            return 1
        # 基准情况2：s遍历完了但t还没匹配完，没有有效子序列
        if i == n:
            return 0
        
        # 情况1：不选s[i]，直接递归处理s的下一位
        result = dp(i + 1, j)
        
        # 情况2：如果s[i]和t[j]相等，可以选择选s[i]，递归处理两者的下一位
        if s[i] == t[j]:
            result += dp(i + 1, j + 1)
        
        return result
    
    return dp(0, 0)

思路解释 #

• dp(i, j)的含义是：从s[i:]（s从第i位到末尾）中，匹配t[j:]（t从第j位到末尾）的不同子序列数量。
• 记忆化缓存会自动存储已经计算过的(i,j)组合的结果，避免重复计算相同状态。
• 时间复杂度降到了O(n*m)，空间复杂度也是O(n*m)（缓存的状态总数）。

自底向上的动态规划解法（可选） #

如果你不想用递归，也可以用二维数组实现自底向上的动态规划，同样高效：

def numDistinct(self, s: str, t: str) -> int:
    n = len(s)
    m = len(t)
    if n < m:
        return 0
    
    # dp[i][j]表示s的前i个字符中，匹配t的前j个字符的子序列数量
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    # 初始化：空字符串是任何字符串的子序列，所以所有dp[i][0] = 1
    for i in range(n + 1):
        dp[i][0] = 1
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 不选s的第i个字符（对应s[i-1]），继承上一行的结果
            dp[i][j] = dp[i-1][j]
            
            # 如果当前字符匹配，加上选这个字符的情况（来自上一行前一列的结果）
            if s[i-1] == t[j-1]:
                dp[i][j] += dp[i-1][j-1]
    
    return dp[n][m]

思路解释 #

• 初始化dp[i][0] = 1是因为空字符串是任何字符串的子序列，数量为1。
• 双层循环遍历每个字符，逐步填充dp数组，状态转移逻辑和递归版完全一致。

内容的提问来源于stack exchange，提问作者Sumeet Bisen