字符串 + 动态规划

class Solution {
public:
    int numDistinct(string s, string t) {           
        int s_len = s.size(), t_len = t.size();
        long f[t_len + 1][s_len + 1];           //数组比vector快一点
        memset(f, 0, sizeof f);                 // f[i][j]表示在s[0~j]的子序列中t[0~i]出现的个数

        for (int i = 0; i < s_len; i ++ ) f[0][i] = 1;  //匹配串为空时初始化匹配个数为1

        for (int i = 1; i <= t_len; i ++ )
            for (int j = 1; j <= s_len; j ++ )
                if (s[j - 1] == t[i - 1])                       
                    f[i][j] = f[i - 1][j - 1] + f[i][j - 1];
                else 
                    f[i][j] = f[i][j - 1];

        return f[t_len][s_len];
    }
};