解题思路
使用缓存避免重复计算
定义一个函数，计算s的某区间包含t的某区间多少次
细节如代码中的注释
115. 不同的子序列
代码
class Solution(object):
def numDistinct(self, s, t):
cache = {}
def dp(s, t, sb, tb, se, te):
key = (sb, tb, se, te)
if key not in cache:
if tb > te: cache[key] = 1 # t的所有字符都看完了
elif sb > se: cache[key] = 0 # t没看完但是s看完了
elif se - sb < te - te: cache[key] = 0 # t剩下的比s剩下的长度还长
elif s[sb] != t[tb]: # 从生于的s里继续搜索t
cache[key] = dp(s, t, sb+1, tb, se, te)
else:
x = dp(s, t, sb+1, tb+1, se, te) # case1: s和t都消除匹配的字符
y = dp(s, t, sb+1, tb, se, te) # case2: 保留完整的t继续查找
cache[key] = x + y
return cache[key]
return dp(s, t, 0, 0, len(s) - 1, len(t) - 1)
效果图
