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.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;class Solution {private:    // only used by dfs    int *memo;    int cols;public:    // 1. dfs    int numDistinct(string S, string T) {        int ret = 0;        cols = T.length();        int msize = S.length() * cols;        memo = new int[msize];        memset(memo, -1, msize * sizeof(int));        ret = dfs(S, 0, T, 0);        delete[] memo;        return ret;    }        int dfs(string& S, int pa, string& T, int pb) {                if (pb >= T.size()) {            return 1;        }        if (pa >= S.size()) return 0;        if (memo[pa * cols + pb] != -1) return memo[pa * cols + pb];        int r = 0;        if (S[pa] == T[pb]) {            r += dfs(S, pa + 1, T, pb + 1);        }        r += dfs(S, pa + 1, T, pb);        memo[pa * cols + pb] = r;        return r;    }        // 2. dynamic programming    int _numDistinct(string S, string T) {        int ret = 0;        int rows = S.length() + 1;        int cols = T.length() + 1;        int* dp = new int[rows * cols];                for (int i=0; i
        
       
      
     

跟往常一样凡是能用dfs+memo解决的，都可以改写为动态规划的形式，实质上即一个问题有最优子问题组成的解。

隔了一年想不起来了，dp看来还是无法掌握，IQ有限：

class Solution {public:    int numDistinct(string s, string t) {        int slen = s.size();        int tlen = t.size();                vector
     
      
        > dp(slen + 1, vector
       
        (tlen + 1, 0));        for (int i=0; i <= slen; i++) {            dp[i][0] = 1;        }        for (int i=1; i<=slen; i++) {            for (int j=1; j<=tlen; j++) {                dp[i][j] = dp[i-1][j] + (s[i-1] == t[j-1] ? dp[i-1][j-1] : 0);            }        }        return dp[slen][tlen];    }};