# 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 };``````