Distinct Subsequences

来源：Leetcode

原帖：https://oj.leetcode.com/problems/distinct-subsequences/

题目：
Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.

代码：

 class Solution {  
 public:  
   //dp. T[i] 前i个字符 与 S[j] 前j个字符的匹配  
   int numDistinct(string S, string T) {  
     int N = S.size(), M = T.size();  
     int dp[M + 1][N + 1];  
     for (int j = 0; j <= N; ++j) {  
       dp[0][j] = 1; // starting with 0        
     }  
     for (int i = 1; i <= M; ++i) {  
       dp[i][0] = 0; // starting with 1        
     }  
     for (int i = 1; i <= M; ++i) { // size of T  
       for (int j = 1; j <= N; ++j) {// size of S  
         if (S[j - 1] == T[i - 1]) {  
           dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];            
         } else {  
           dp[i][j] = dp[i][j - 1];            
         }  
       }  
     }  
     return dp[M][N];  
   }  
 };