@@ -0,0 +1,1635 @@
+package com.fulin.DP;%0A%0A/**%0A * 115. Distinct Subsequences%0A *%0A * Given a string S and a string T, count the number of distinct subsequences of S which equals T.%0A * 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, %22ACE%22 is a subsequence of %22ABCDE%22 while %22AEC%22 is not).%0A * Here is an example:%0A * S = %22rabbbit%22, T = %22rabbit%22%0A * Return 3%0A *%0A * Created by fulin on 17-8-16.%0A */%0Apublic class DistinctSubsequences %7B%0A%0A    public int numDistinct(String s, String t) %7B%0A%0A        // %E5%A6%82%E6%9E%9Ct %E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%BA%E7%A9%BA%E5%AD%97%E7%AC%A6%E4%B8%B2%EF%BC%8C%E5%88%99%E8%BF%94%E5%9B%9E1%0A        if(t == null %7C%7C t.length()  == 0)%7B%0A            return 1;%0A        %7D%0A%0A        //%E5%A6%82%E6%9E%9Ct %E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%8D%E4%B8%BA%E7%A9%BA%EF%BC%8Cs%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%BA%E7%A9%BA%EF%BC%8C%E5%88%99%E8%BF%94%E5%9B%9E0%0A        if(s == null %7C%7C s.length() == 0)%7B%0A            return 0;%0A        %7D%0A%0A        //%E5%A6%82%E6%9E%9Cs%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E9%95%BF%E5%BA%A6%E5%B0%8F%E4%BA%8Et%E7%9A%84%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E9%95%BF%E5%BA%A6%EF%BC%8C%E5%88%99%E8%BF%94%E5%9B%9E0%0A        if(s.length() %3C t.length())%7B%0A            return 0;%0A        %7D%0A        //%E5%A6%82%E6%9E%9C%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%AE%8C%E5%85%A8%E7%9B%B8%E5%90%8C%EF%BC%8C%E5%88%99%E8%BF%94%E5%9B%9E1%0A        if(t.equals(s))%7B%0A            return 1;%0A        %7D%0A        int m = s.length();%0A        int n = t.length();%0A%0A        int%5B%5D%5B%5D nums = new int%5Bm +  1%5D%5Bn + 1%5D;%0A%0A        nums%5B0%5D%5B0%5D = 1;%0A%0A        for(int i = 1;i%3C= m ; i++)%7B%0A            nums%5Bi%5D%5B0%5D = 1;%0A        %7D%0A%0A        for(int i=1 ;i%3C=n ;i++)%7B%0A            nums%5B0%5D%5Bi%5D = 0;%0A        %7D%0A%0A        for(int i=1;i%3C=m;i++)%7B%0A            for(int j=1;j%3C=n;j++)%7B%0A                if(s.charAt(i-1) == t.charAt(j-1))%7B%0A                    nums%5Bi%5D%5Bj%5D = nums%5Bi - 1%5D%5Bj - 1%5D + nums%5Bi - 1%5D%5Bj%5D ;%0A                %7Delse%7B%0A                    nums%5Bi%5D%5Bj%5D = nums%5Bi - 1%5D%5Bj%5D;%0A                %7D%0A            %7D%0A        %7D%0A%0A%0A        return nums%5Bm%5D%5Bn%5D;%0A    %7D%0A%7D%0A

leetcode :115. Distinct Subsequences