This is similar to Edit Distance problem we solved before, which also needs to build dp array, however, here, from s to t, we can only perform delete operation.

dp array: `dp[i][j]`

means the number of distinct subsequences of `t.substr(0, i)`

in `s.substr(0,j)`

. if `i = 0`

, `t.substr(0,0) = ""`

, we can say there are 1 instance of that for "". So, initialize `dp[0][j] = 1`

, and other `dp[i][j] = 0`

.

dp[1][1]: how many A in "A"? It's obvious, dp[1][1] = 1;

dp[1][2]: how many A in "AE"? It's obvious, dp[1][2] = dp[1][1] = 1;

dp[1][3]: how many A in "AECD"? similarly, dp[1][3] = dp[1][2];

... ...

dp[2][6]: how many "AE" in "AECDEE"? Since the end of "AECDEE" matches end of "AE", consider the purpose we build dp, we want to use the result we already calculated, so we can split this into two subproblems:

- if 'E' in "A
`E`

" comes from last 'E' in "AECDE`E`

"

here, we can then disregard the last 'E' in both sub-string, the answer for this subproblem should be equivalent to calc `dp[i - 1][j - 1]`

: how many "A" in "AECDE"?

- if 'E' in "AE" comes from "A
`E`

CD`E`

"

here, the answer for this subproblem should be equivalent to calc `dp[i][j - 1]`

: how many "AE" in "AECDE"?

```
dp[2][6] = dp[1][5] + dp[2][5] = 1 + 2 = 3
```

Based on above scenarios, we get the following generalized rules

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

Build dp array

```
A E C D E E C E
0 1 2 3 4 5 6 7 8
0 1 1 1 1 1 1 1 1 1
A 1 0 1 1 1 1 1 1 1 1
E 2 0 0 1 1 1 2
C 3
```

Final table

```
A E C D E E C E
0 1 2 3 4 5 6 7 8
0 1 1 1 1 1 1 1 1 1
A 1 0 1 1 1 1 1 1 1 1
E 2 0 0 1 1 1 2 3 3 4
C 3 0 0 0 1 1 1 1 4 4
```

Code

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