115. 不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 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

提示：

• 1 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

动态规划-函数递归-倒序遍历+备忘录

class Solution {
    public int numDistinct(String s, String t) {
        int sLen = s.length(), tLen = t.length();

        // 初始化 memo 数组，用于存储中间结果，避免重复计算
        int[][] memo = new int[sLen][tLen];
        for (int i = 0; i < sLen; i++) {
            for (int j = 0; j < tLen; j++) {
                memo[i][j] = -1; // 初始化 memo 数组为 -1，表示未计算过。Arrays.fill只能填充一维数组
            }
        }

        // 计算 s 中出现 t 的不同子序列的个数
        return helper(s, t, sLen - 1, tLen - 1, memo);
    }

    // 辅助递归函数，计算 s[0..i] 中出现 t[0..j] 的不同的次数
    private int helper(String s, String t, int i, int j, int[][] memo) {
        if (j < 0) { // t 被完全匹配，找到一个有效的子序列
            return 1;
        }
        if (i < 0) { // s 被用尽，无法继续匹配
            return 0;
        }
        if (memo[i][j] != -1) { // 检查 memo 中是否已经计算过该子问题
            return memo[i][j];
        }
        
        if (s.charAt(i) == t.charAt(j)) { // 当前字符匹配
            // 计算两种情况：不使用 s[i] 匹配 t[j] 和使用 s[i] 匹配 t[j]。这个和最长公共子序列不一样，
            // 这个只能是s包含t，t不可能包含s，所以不用考虑 helper(s, t, i, j-1, memo)，然后注意这里是求总和而不是求最值。
            // 重点。
            memo[i][j] = helper(s, t, i - 1, j, memo) + helper(s, t, i - 1, j - 1, memo);
        } else { // 当前字符不匹配，只能不使用 s[i]，注意j不变！
            memo[i][j] = helper(s, t, i - 1, j, memo);
        }
        
        return memo[i][j]; // 返回计算结果并存储在 memo 中
    }
}

动态规划-数组递推-倒序遍历

class Solution {
    public int numDistinct(String s, String t) {
        int sLen = s.length();  // s 字符串的长度
        int tLen = t.length();  // t 字符串的长度

        // dp[i][j] 表示在 s 的前 i 个字符中，t 的前 j 个字符出现的次数
        int[][] dp = new int[sLen + 1][tLen + 1];

        // 遍历每个字符的组合，填充 dp 数组
        for (int i = 0; i <= sLen; i++) {
            for (int j = 0; j <= tLen; j++) {
                if (j == 0) { // 重点。基本情况1：t 为空字符串，空字符串是任何字符串的子序列，所以 dp[i][0] = 1
                    dp[i][j] = 1;
                } else if (i == 0) { // 重点。基本情况2：s 为空字符串，t 非空，显然不能形成子序列，所以 dp[0][j] = 0
                    dp[i][j] = 0;
                } else {
                    // 如果 s[i-1] == t[j-1]，可以有两种选择：
                    // 1. 使用 s[i-1] 作为 t[j-1]，所以子问题为 dp[i-1][j-1]
                    // 2. 不使用 s[i-1]，直接看 s[i-1] 之前的字符能否组成 t[j]，即 dp[i-1][j]
                    if (s.charAt(i - 1) == t.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                    } else {
                        // 如果 s[i-1] != t[j-1]，只能跳过 s[i-1]，子问题为 dp[i-1][j]。注意j不变！
                        // 重点
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
        }

        // dp[sLen][tLen] 表示 s 的前 sLen 个字符中 t 的前 tLen 个字符出现的次数
        return dp[sLen][tLen];
    }
}

空间压缩

从后往前遍历。

class Solution {
    public int numDistinct(String s, String t) {
        int sLen = s.length(), tLen = t.length();

        // 一维dp数组
        int[] dp = new int[tLen + 1];
        dp[0] = 1; // 初始化 base case

        for (int i = 1; i <= sLen; i++) {
            // 从后向前更新，防止覆盖还需要使用的数据
            // 之所以要从后往前，是因为我们要用dp[i-1][j-1]而不是dp[i][j-1]，此时dp[j-1]还没有被更新，所以是上一轮的dp[j-1]，即dp[i-1][j-1]
            // 如果是从前往后，则计算dp[j]时已经更新过了dp[j-1]，所以此时dp[j-1]是本轮的dp[j-1]，即dp[i][j-1]。
            for (int j = tLen; j >= 1; j--) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    // dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                    dp[j] = dp[j - 1] + dp[j];
                } // 否则 dp[j] 不变
            }
        }

        return dp[tLen]; // 前 sLen 个字符的 s 串中，出现前 tLen 个字符的 t 串的次数
    }
}

从前往后遍历。

class Solution {
    public int numDistinct(String s, String t) {
        int sLen = s.length(), tLen = t.length();

        // 一维dp数组
        int[] dp = new int[tLen + 1];
        dp[0] = 1; // 初始化 base case

        for (int i = 1; i <= sLen; i++) {
            int prev = dp[0]; // 保存上一行的dp[j-1]
            for (int j = 1; j <= tLen; j++) {
                int temp = dp[j]; // 保存当前dp[j]，用于下一次迭代的prev
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j] = prev + dp[j];
                }
                prev = temp; // 更新prev为当前行的dp[j-1]
            }
        }

        return dp[tLen]; // 前 sLen 个字符的 s 串中，出现前 tLen 个字符的 t 串的次数
    }
}