First, the naive solution with `memo`

, AC in 1250~ms, pretty slow right?

```
class Solution(object):
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
def helper(i, j):
if j == n2: return 1
if (i, j) not in memo:
memo[(i, j)] = sum(helper(k+1, j+1) for k in range(i, n1) if s[k] == t[j])
return memo[(i, j)]
n1, n2 = len(s), len(t)
memo = {}
return helper(0, 0)
```

Let's try 2D DP. This one use O(m*n) space and AC in 250~ms.

```
class Solution(object):
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
n1, n2 = len(s), len(t)
dp = [[1] * (n2+1) for i in range(n1+1)]
for j in range(1, n2+1):
dp[0][j] = 0
for i in range(1, n1+1):
for j in range(1, n2+1):
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * (s[i-1] == t[j-1])
return dp[-1][-1]
```

As always, 2D DP can be converted into 1D DP mostly. This one use O(n) space and AC in 200~ms.

```
class Solution(object):
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
n1, n2 = len(s), len(t)
dp = [1] + [0] * n2
for i in range(1, n1+1):
pre = dp[0]
for j in range(1, n2+1):
dp[j], pre = dp[j] + pre * (s[i-1] == t[j-1]), dp[j]
return dp[-1]
```