115. Distinct Subsequences

dp[i][j] is the number of distinct subsequences of T[0, j] in S[0, i].
So if T[j] == S[i], then dp[i][j] is the number of distinct subsequences of T[0, j-1] in S[0, i-1] plus the number of distinct subsequences of T[0, j] in S[0, i-1]. Otherwise, dp[i][j] is the number of distinct subsequences of T[0, j] in S[0, i-1].

1:  class Solution {  
2:  public:  
3:    int numDistinct(string s, string t) {  
4:      int rows = s.size();  
5:      int cols = t.size();  
6:      if (cols > rows) return 0;  
7:      vector<vector<int>> dp(rows, vector<int>(cols, 0));  
8:      if (t[0] == s[0]) dp[0][0] = 1;  
9:      for (int i = 1; i < rows; i++) {  
10:        dp[i][0] = (t[0] == s[i]) ? dp[i-1][0]+1 : dp[i-1][0];  
11:      }  
12:      for (int j = 1; j < cols; j++) {  
13:        for (int i = 1; i < rows; i++) {  
14:          dp[i][j] = (t[j] == s[i]) ? dp[i-1][j-1]+dp[i-1][j] : dp[i-1][j];  
15:        }  
16:      }  
17:      return dp[rows-1][cols-1];  
18:    }  
19:  };