LC 0115 [H] Distinct Subsequences - ALawliet/algorithms GitHub Wiki
class Solution:
def numDistinct(self, s: str, t: str) -> int:
@cache
def dp(i, j) -> int:
if j == len(t):
return 1
if i == len(s): # exhausted the source without matching the target
return 0
skip = delete = dp(i+1, j) # delete or skip past the source, but still have to find the char in the target
match = dp(i+1, j+1) # can increment both source and target
if s[i] == t[j]:
res = match + skip # or
else:
res = delete
return res
return dp(0, 0)