092. Distinct Subsequences/solution.h

#include <string>
using std::string;
#include <vector>
using std::vector;

class Solution {
public:
    int numDistinct(string S, string T) {
        int m = static_cast<int>(S.size());
        int n = static_cast<int>(T.size());
        if (m < n) return 0;
        vector<int> v(n+1, 0); v[0] = 1;
        for (int i=1; i<=m; ++i)
            for (int j=std::min(i, n)+1; j>0; --j)
                if(S[i-1] == T[j-1]) v[j] += v[j-1];
        
        return v.back();
    }
};