[leetcode]Distinct Subsequences

此题是DP，有了Edit Distance（http://www.cnblogs.com/lautsie/p/3251311.html）的经验，照理说是能想出来的，但我把字符串分两份后就开始想左边的数目乘以右边的数目，这思路是不对的，是分治的思路，而这种DP的话，是多了一个后，用之前的一两个的状态来计算。

所以状态转移方程式dp[i][j]=dp[i-1][j] (s[i-1] != t[j-1]时)或dp[i][j] = dp[i-1][j-1]+dp[i-1][j] (s[i-1]==t[j-1]时)。其中dp[i][j]表示S和T长度为i和j时的Distinct SubSequences。那么如果最后一个字符不相等，就把S的这个字符去掉，看之前的能否相等；如果相等，就分两种情况，S和T的最后一个字符同时去掉或者S的这个字符留下。（看来字符串的DP经常用字符是不是相等来区分）

public class Solution {
    public int numDistinct(String S, String T) {
        int sLen = S.length();
        int tLen = T.length();
        int[][] mx = new int[sLen+1][tLen+1];
        mx[0][0] = 1;
        for (int i = 1; i <= sLen; i++)
        {
            mx[i][0] = 1;
        }
        for (int j = 1; j <= tLen; j++)
        {
            mx[0][j] = 0;
        }

        for (int i = 1; i <= sLen; i++)
        {
            for (int j = 1; j <= tLen; j++)
            {
                if (i < j) mx[i][j] = 0;
                else if (S.charAt(i-1) != T.charAt(j-1))
                {
                    mx[i][j] = mx[i-1][j];
                }
                else
                {
                    mx[i][j] = mx[i-1][j-1] + mx[i-1][j];
                }
            }
        }
        return mx[sLen][tLen];
    }
}