# Easy C++ DP solution, O(N) space, O(MN) time

• 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]`.

1. If `s[i] == t[j]`, consider `s(i-1) s[i]` and `t(j-1) t[j]`.
1. There are `dp(i-1, j-1)` subsequence pairs ending with exactly `s[i]` and `t[j]`.
2. There are `dp(i-1, j)` subsequence pairs ending with a letter in `s(i-1)` and `t[j]`.
3. So, `dp(i,j) = dp(i-1, j-1) + dp(i-1, j)`
2. 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:

1. When matching `s` with `""`, regard there is one DS, i.e. `dp(i, 0) = 1` (Specially `dp(0, 0) = 1`)
2. 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];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.