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.
Here is an example:
S ="rabbbit", T ="rabbit"
Return3.

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size();
        int n = t.size();
        vector<vector<int>> f(m+1,vector<int>(n+1,0));
        for(int i =0;i<m+1;i++)
          f[i][0] = 1;
        
        for(int i=1;i<m+1;i++)
          for(int j=1;j<n+1;j++)
          {
              if(s[i-1]==t[j-1])
                f[i][j] = f[i-1][j-1] + f[i-1][j];//两种方式可以到达f[i][j],因为S的长度大于T，所以不可能有f[i][j-1]
              else
                f[i][j] = f[i-1][j];  //只有一种方法到达f[i][j]
          }
        return f[m][n];
    }
};