distinct-subsequences

https://leetcode.com/problems/distinct-subsequences/
给定字符串s和t，求s的子串中有多少种方式能变成t

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

解析

public int numDistinct(String s, String t) {
        //递推公式
        //dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0)

        int[][] dp = new int[t.length() + 1][s.length() + 1];

        //空字符串是任何字符串的子串
        for (int j = 0; j < s.length() + 1; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i < t.length() + 1; i++) {
            for (int j = 1; j < s.length() + 1; j++) {

                if (t.charAt(i - 1) == s.charAt(j - 1)) {

                    dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
                } else {
                    //因为s新增的一位字符不等于t新增的一位，
                    //所以并没有对子字符串带来新的可能性
                    //所以个数就以左边那个值为准(s减少了一位，t没变)
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[t.length()][s.length()];
    }