1. Title Description

Given a string S And a string T, Calculated at S In the subsequence of T Number of occurrences .

A subsequence of a string refers to , By deleting some （ It can also be done without deleting ） Character and does not interfere with the relative position of the remaining characters of the new string .（ for example ,“ACE” yes “ABCDE” A subsequence of , and “AEC” No ）

Example 1:
Input : S = “rabbbit”, T = “rabbit”
Output : 3
explain :
As shown in the figure below , Yes 3 Species can be obtained from S Get in “rabbit” The plan .
( Up arrow sign ^ Indicates the selected letter )

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Example 2:
Input : S = “babgbag”, T = “bag”
Output : 5
explain :
As shown in the figure below , Yes 5 Species can be obtained from S Get in “bag” The plan .
( Up arrow sign ^ Indicates the selected letter )

babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^

2. Ideas

Sketch Map ：

2.1 Code

class Solution:
def numDistinct(self, s: str, t: str) -> int:
if t == "" and s == "":
return 0
if t == "":
return 1
dp = [[0 for i in range (len(s)+1)] for j in range(len(t)+1) ]
for j in range(0,len(s)+1):
dp[0][j] = 1
for i in range(1,len(t)+1):
for j in range(1,len(s)+1):
dp[i][j] = dp[i][j-1]
if s[j-1] == t[i-1]:
dp[i][j] += dp[i-1][j-1]
return dp[-1][-1]

Look at other people's analysis , Discovery can also be optimized , And then there's the algorithm from the tail . I'll update it later .