LeetCode：115.不同的子序列

跟着carl学算法，本系列博客仅做个人记录，建议大家都去看carl本人的博客，写的真的很好的！
代码随想录

LeetCode：115.不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
示例 1：
输入：s = “rabbbit”, t = “rabbit”
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
rabbbit
rabbbit
rabbbit
示例 2：
输入：s = “babgbag”, t = “bag”
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 “bag” 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag

• dp[i][j]表示在s[0]到s[i - 1]的所有子序列中有t[0] 到t[j - 1]的子序列的个数是dp[i][j]个
• 初始化：dp[i][0] = 1即当s不为空，t为空时有1个不同的子序列
• 递推公式：当s.charAt(i - 1) == t.charAt(j - 1) 即字符相同时，dp[i][j]可以有两种方式组成：考虑当前元素(dp[i - 1][j - 1)和不考虑当前元素(dp[i - 1][j])； 当两个字符不相同时，dp[i - 1][j]

	public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[s.length()][t.length()];
    }