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

Loading Disqus comments...
Table of Contents