**Solution**

**Distinct Subsequences** https://leetcode.com/problems/distinct-subsequences/?tab=Description

**Question**

- This question requires re-wording. Here is a better description http://www.programcreek.com/2013/01/leetcode-distinct-subsequences-total-java/:

"Given a string S and a string T, count the number of distinct subsequences of S which equals T."

"How many ways can you generate the string T by only removing (but not reordering) characters in S?"

**Dynamic Programming**

- The next thing we need to do is come up with a way to divide this problem and subsequently come up with a recurrence.
- dp[i,j]: How many subsequences of s[0:j-1] are equal to t[0:i-1]?
- dp[i,j] = dp[i-1,j-1] + dp[i, j-1] if t[i-1] == s[j-1]
- dp[i,j] = dp[i, j-1] if t[i-1] != s[j-1]
- Note i and j are respective lengths.
- What are the boundary conditions? Refer to code.
- What is the order of filling up the array? row-wise.
- Picture and explanation:https://discuss.leetcode.com/topic/9488/easy-to-understand-dp-in-java
- Another explanation:https://discuss.leetcode.com/topic/6465/a-dp-solution-with-clarification-and-explanation

```
class Solution(object):
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
N, M = len(t), len(s)
dp = [[0]*(M+1) for _ in range(N+1)]
for i in range(N+1):
dp[i][0] = 0 # How many subsequences of zero length S can be formed which equal t[0:i]
for j in range(M+1):
dp[0][j] = 1 # How many subsequences of S[0:j] can be formed which equal t[0:1]
for i in range(1, N+1):
for j in range(1, M+1):
if t[i-1] == s[j-1]:
dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
else:
dp[i][j] = dp[i][j-1]
return dp[N][M]
```

**Memoization**

```
from collections import defaultdict
class Solution(object):
def helper(self, i, j, s, t, cache):
if i == len(s) and j == len(t):
return 1
elif i == len(s):
return 0
elif j == len(t):
return 1
elif i in cache and j in cache[i]:
return cache[i][j]
elif s[i] == t[j]:
# Include or Do Not Include
return self.helper(i+1, j+1, s, t, cache) + self.helper(i+1, j, s, t, cache)
else:
return self.helper(i+1, j, s, t, cache)
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
cache = defaultdict(dict)
return self.helper(0,0,s,t,cache)
```