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.

使用动态规划算法思考的题目。因为如果知道T的子串在S以及其子串中distinct subsequences个数，那么T在S中的distinct subsequences个数也能通过它算出来。关键是如何找出转移函数。

使用题目中的例子，考虑简单的情况，S=rab，T=rab时，很明显number=1. 当S=rabb（多加一位）后，原有的number依然会有，因为rab还是能跟rab匹配。然而因为新加的字符与T的最后一个字符一样，这个时候T最后一个字符可以去匹配新加的字符，这个是在之前没有的情况，需要额外考虑。那么，多出来的distinct subsequences数就应该是排除掉T最后一个字符（匹配新字符去了）以及S中的新添加字符后的个数，即为S=rab,T=ra的情况。总的个数就是原来的number加上S=rab,T=ra情况下的个数。

如果S多加的一位不是T的最后一位字符，那么就不会有多出来的情况，这时候的distinct subsequences个数应该还是原来的个数。

创建一个二维数组，dp. dp[i][j]表示T.substring(0,i)和S.substring(0,j)的情况，0<=i<=T.length(), 0<=j<=S.length().

dp[i][j] = dp[i][j-1]　　//原有情况

　　　　+   dp[i-1][j-1]  //如果T.charAt(i-1)==S.charAt(j-1)

起始情况dp[0][j]=1, 因为T为空字符串时匹配个数始终为1.

dp[i][j]=0如果j<i因为当T长度大于S肯定没有这样的subsequences.

代码如下：

 1     public int numDistinct(String S, String T) { 2         if(T.length()>S.length()) 3             return 0; 4         int[][] dp = new int[T.length()+1][S.length()+1]; 5         for(int i=0;i<=T.length();i++) { 6             for(int j=i;j<=S.length();j++) { 7                 if(i==0) 8                     dp[i][j]=1; 9                 else10                     dp[i][j] = dp[i][j-1]+(T.charAt(i-1)==S.charAt(j-1)?dp[i-1][j-1]:0);11             }12         }13         return dp[T.length()][S.length()];14     }

因为每次循环只需要拿到上一次的dp值，所以可以对空间复杂度进一步优化：

 1     public int numDistinct(String S, String T) { 2         int m = T.length(); 3         int n = S.length(); 4         if(m>n) 5             return 0; 6         int[] dp = new int[m+1]; 7         dp[0] = 1; 8         for(int j=1;j<=n;j++) 9         {10             for(int i=m;i>0;i--)11             {12                 dp[i] += (T.charAt(i-1)==S.charAt(j-1))?dp[i-1]:0;13             }14         }15         return dp[m];16     }

[Leetcode][JAVA] Distinct Subsequences