理解不同子序列DP基准情况：两种DP写法边界条件差异解析

我在解决LeetCode的「不同子序列问题」：给定两个字符串s和t，返回s的子序列中等于t的不同子序列数目。例如s="rabbbit"、t="rabbit"时答案为3。

先实现了可行的自底向上DP解法：

# bottom up - working
def numDistinct(self, s: str, t: str) -> int:
    
    @cache # (i,j): number of distinct subsequences in s[i:] that equal t[j:]
    def aux(i, j):            
        if j == len(t): return 1 
        if i == len(s): return 0 
        
        if s[i] == t[j]:
            return aux(i+1, j+1) + aux(i+1, j)
        else:
            return aux(i+1, j)
        
    return aux(0,0)

该解法通过了测试。随后尝试自顶向下DP解法，初始版本无法得到正确结果（上述示例输出为0而非3）。通过手动推演，修改边界条件后解法可行：

# top down - working
def numDistinct(self, s: str, t: str) -> int:

    @cache        
    def aux(i, j):
        
        if i == -1: return 1 if j == -1 else 0 # if s exhausts before t, return 0, else 1
        if j == -1: return 1
        
        if s[i] == t[j]:
            return aux(i-1,j-1) + aux(i-1, j)
        else:
            return aux(i-1, j)
        
    return aux(len(s)-1, len(t)-1)

疑问解析 #

核心原因是边界判断的优先级和递归的逻辑路径差异：

在自底向上的递归逻辑中，我们先判断if j == len(t): return 1——这意味着只要t已经完全匹配完成（j走到了末尾），不管s有没有剩余（i是否到末尾），都直接返回1，因为空的t本身就是任何s的子序列。

当执行到if i == len(s): return 0的时候，说明前面的j == len(t)判断没有触发，也就是j还没走到t的末尾。此时s已经耗尽，不可能再匹配出剩下的t[j:]，所以直接返回0就足够，不需要额外判断j的状态。

反观自顶向下的递归，我们从字符串末尾往开头遍历，边界是i=-1（s遍历完）和j=-1（t遍历完）：

• 如果j=-1，说明t已经匹配完，不管s有没有剩余，都返回1；
• 如果i=-1但j≠-1，说明s耗完了但t还没匹配完，返回0；
  这两种情况必须分开判断，因为递归路径里可能先走到i=-1的状态，此时需要明确j的状态才能返回正确结果。

简单来说，自底向上的递归里，j == len(t)的判断优先级更高，已经覆盖了所有“t匹配完成”的场景，剩下的i到末尾的情况必然是t未匹配完成，所以直接返回0即可。

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