【LeetCode】不同的子序列 [H]（动态规划）

115. 不同的子序列 - 力扣（LeetCode）

一、题目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 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

提示：

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

二、代码

class Solution {
    public int numDistinct(String sStr, String tStr) {
        if (sStr == null || tStr == null || sStr.length() == 0 || tStr.length() == 0) {
            return 0;
        }
 
        char[] s = sStr.toCharArray();
        char[] t = tStr.toCharArray();
        
        // dp[i][j] : s只拿前i个字符做子序列，有多少个子序列，字面值等于T的前j个字符的前缀串
        int[][] dp = new int[s.length][t.length];
 
        // 第0行，除了dp[0][0]，如果S的0下标等于T的0下标，那么dp[0][0] = 1，否则等于0。其余第0行位置都是0，因为一个字符不可能和多个字符组成的字符串相等。
        dp[0][0] = s[0] == t[0] ? 1 : 0;
        // dp[0][j] = s只拿前0个字符做子序列, T前j个字符
        // 从i=0开始向下遍历，只要是遍历到的格子对应的s字符串的字符位置，s的这个字符等于T字符串0下标位置的字符的话，当前格子就是上面格子的数+1，不相等，当前格子就等于上面的格子。其实就是相当于找S字符串上有多少个等于T字符串0下标的字符。
        for (int i = 1; i < s.length; i++) {
            dp[i][0] = s[i] == t[0] ? (dp[i - 1][0] + 1) : dp[i - 1][0];
        }
 
        // S[...i]的所有子序列中，包含多少个字面值等于T[...j]这个字符串的子序列，记为dp[i][j]
        // 可能性1）S[...i]的所有子序列中，都不以s[i]结尾，则dp[i][j]肯定包含dp[i-1][j]
        // 可能性2）S[...i]的所有子序列中，都必须以s[i]结尾，
        // 这要求S[i] == T[j]，则dp[i][j]包含dp[i-1][j-1]
        for (int i = 1; i < s.length; i++) {
            // 不能超过t的最长范围，也不能超过此时s字符串0~i的范围长度（t字符串0~j前缀长度如果超过了s字符串0~i的长度，那么就不可能存在相等字面值的情况），所以就从i和t.length - 1中取最小值，i和t.length-1都是值的下标，所以j都是小于等于他们
            for (int j = 1; j <= Math.min(i, t.length - 1); j++) {
                // 情况1
                dp[i][j] = dp[i - 1][j];
                // 情况2
                if (s[i] == t[j]) {
                    // 情况1和情况2加和
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
        return dp[s.length - 1][t.length - 1];
    }
}

三、解题思路 

dp[i][j]：s字符串0...i这个范围要搞子序列，i往后范围不可使用，有多少个子序列的字面值等于字符串t从0到j这个前缀字符串。

一共有两种情况：

1. 子序列不考虑i位置的字符。dp[i][j] = dp[i - 1][j]
2. 子序列一定要含有i位置的字符

• [i]位置字符跟j位置字符不相等，那么可能性2）就一定不成立
• [i]位置字符跟j位置字符相等，可能性2）才有可能成立。dp[i][j] = dp[i - 1][j - 1]