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).

leetcode_distinct_subsequences.cpp

class Solution {
public:
    int numDistinct(string S, string T) {
        int n = S.length();
        int m = T.length();
        if (n == 0 || m == 0)
            return 0;
        int **f = new int*[n];
        for (int i = 0; i < n; ++i)
            f[i] = new int[m];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                f[i][j] = 0;
                if (S[i] == T[j]) {
                    if (j == 0)
                        f[i][j] += 1;
                    else if (i != 0)
                        f[i][j] += f[i - 1][j - 1];
                }
                if (i != 0)
                    f[i][j] += f[i - 1][j];
            }
        int ret = f[n - 1][m - 1];
        for (int i = 0; i < n; ++i)
            delete[] f[i];
        delete[] f;
        return ret;
    }
};