Distinct Subsequences

題目：

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.

代碼如下：

int DP(int m,int n,int **a,string &S, string &T)
    {
        if(n == -1)
            return 1;
        else if(m == -1)
            return 0;
        if(m < n)
            return 0;
        if(a[m][n] != -1)
            return a[m][n];
        if(S[m]==T[n])
        {
            a[m][n] = DP(m-1,n,a,S,T)+DP(m-1,n-1,a,S,T);
            return a[m][n];
        }
        else
        {
            a[m][n] = DP(m-1,n,a,S,T);
            return a[m][n];
        }
    }
    int numDistinct(string S, string T) {
        int **a=new int*[S.length()];
        for(int i = 0;i < S.length();i++)
            a[i] = new int[T.length()];
        for(int i = 0;i < S.length();i++)
            for(int j = 0;j < T.length();j++)
                a[i][j] = -1;
        return DP(S.length()-1,T.length()-1,a,S,T);
    }