@@ -0,0 +1,1252 @@
+package dp;%0A%0A/**%0A * https://oj.leetcode.com/problems/distinct-subsequences/%0A * Given a string S and a string T, count the number of distinct subsequences of T in S.%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%0A * 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 */%0Apublic class DistinctSubsequences %7B%0A    public int numDistinct(String S, String T) %7B%0A        int l1 = T == null ? 0 : T.length();%0A        int l2 = S == null ? 0 : S.length();%0A        if (l1 == 0 %7C%7C l2 == 0) return 0;%0A        int%5B%5D%5B%5D dp = new int%5Bl1 + 1%5D%5Bl2 + 1%5D;%0A        dp%5B0%5D%5B0%5D = 1;%0A        for (int i = 1; i %3C= l1; i++) %7B%0A            dp%5Bi%5D%5B0%5D = 0;%0A        %7D%0A        for (int i = 1; i %3C= l2; i++) %7B%0A            dp%5B0%5D%5Bi%5D = 1;%0A        %7D%0A        for (int i = 1; i %3C= l1; i++) %7B%0A            for (int j = 1; j %3C= l2; j++) %7B%0A                dp%5Bi%5D%5Bj%5D = dp%5Bi%5D%5Bj - 1%5D;%0A                if (T.charAt(i - 1) == S.charAt(j - 1)) %7B%0A                    dp%5Bi%5D%5Bj%5D += dp%5Bi - 1%5D%5Bj - 1%5D;%0A                %7D%0A            %7D%0A        %7D%0A        return dp%5Bl1%5D%5Bl2%5D;%0A    %7D%0A%7D%0A

distinct subsequences