# distinct subsequences

## distinct subsequences

### A little hard dynamic problem

I solved this problem at the first time, but the second time when I meet this, I did not figure it out.T_T

`dp[i][j]`

means how many distinct subsequences of `S.substr(0,j)`

and `T.substr(0,i)`

.`dp[i][j]`

could be transfromed from the below ways(sum them up).

`dp[i][j-1]`

no matter what`S[j-1]`

is.`dp[i][j-1]`

if`S[j-1] == T[i-1]`

.

```
1 class Solution {
2 public:
3 int numDistinct(string S, string T) {
4 int n = T.length();
5 int m = S.length();
6 if ( n > m ) {
7 return 0;
8 }
9 int dp[n+1][m+1];
10 memset(dp,0,sizeof(dp));
11 for ( int i = 0; i <= m; i++ ) {
12 dp[0][i] = 1;
13 }
14 for ( int i = 1; i <= n; i++ ) {
15 for ( int j = 1; j <= m; j++ ) {
16 dp[i][j] = dp[i][j-1];
17 if ( T[i-1] == S[j-1] ) {
18 dp[i][j] += dp[i-1][j-1];
19 }
20 }
21 }
22 return dp[n][m];
23 }
24 };
```