Given a string S and a string T, count the number of distinct subsequences of T in S.

When I read the question again, I found the phrase cited may be wrong. The question asks us to find distinct subsequence of S == T. If we count the number of distinct subsequences of T in S and S = "rabbbit" and T = "rabbit", then "r" is a subsequence of T and will be counted too. That is obviously not what we want.

Then, we can write the relation which is very similar to LCS. I just remove one state transition from LCS and sum them up. Because T could not be subsequence so dp[i][j] can only come from dp[i - 1][j - 1] and dp[i - 1][j - 1]. dp[i][j - 1] cannot be counted because it will lead to miss some letters in T (becoming subsequence).

Recurrence relation:

*dp[i][j] = dp[i - 1][j] +( dp[i - 1][j - 1] if s[i - 1] == s[j - 1])*

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

Space optimization:

The states are only from top and left-top. Thus, 1-D array is enough and uses some temp variables to roll the array all the way down.

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