Let `dp(i,j) := distinct sub-sequences of s(i) and t(j)`

, `s(i)`

is substring `s[0]...s[i]`

.

Let's separate the case according to whether `s[i] == t[j]`

.

- If
`s[i] == t[j]`

, consider`s(i-1) s[i]`

and`t(j-1) t[j]`

.- There are
`dp(i-1, j-1)`

subsequence pairs ending with exactly`s[i]`

and`t[j]`

. - There are
`dp(i-1, j)`

subsequence pairs ending with a letter in`s(i-1)`

and`t[j]`

. - So,
`dp(i,j) = dp(i-1, j-1) + dp(i-1, j)`

- There are
- If
`s[i] != t[j]`

, you have to use`t(j)`

to looks for sub-sequences in`s(i-1)`

, So,`dp(i,j) = dp(i-1, j)`

.

NOTE: in the above analysis, for simplicity, I denote `dp(i,j) := distinct sub-sequences of s(i) and t(j)`

. In the real code, considering the initial values (e.g. `dp(i, 0)`

and `dp(0, j)`

, Actually `dp(i, j) := DS of s(i-1) and t(j-1)`

.

Corner case:

- When matching
`s`

with`""`

, regard there is one DS, i.e.`dp(i, 0) = 1`

(Specially`dp(0, 0) = 1`

) - When matching
`""`

with`t`

, regard there is no DS, i.e.`dp(0, j) = 0`

```
class Solution {
public:
int numDistinct(string s, string t) {
int M = s.size(), N = t.size();
vector<vector<int>> dp(M + 1, vector<int>(N + 1, 0));
for (int i = 0; i <= M; ++i) dp[i][0] = 1;
for (int i = 1; i <= M; ++i) {
for (int j = 1; j <= N; ++j) {
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[M][N];
}
};
```

Since `dp(i,j)`

only depends on `dp(i-1, j-1)`

and `dp(i-1, j)`

, it's easy to reduce the 2D array into 1D.

```
class Solution {
public:
int numDistinct(string s, string t) {
int M = s.size(), N = t.size();
vector<int> dp(N + 1, 0);
dp[0] = 1;
for (int i = 1; i <= M; ++i) {
for (int j = N; j >= 0; --j) {
if (s[i - 1] == t[j - 1]) {
dp[j] += dp[j - 1];
}
}
}
return dp[N];
}
};
```