Leetcode 115.不同的子序列

题目要求

  • 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

  • 测试用例保证结果在 32 位有符号整数范围内。

示例1：
输入：s = “rabbbit”, t = “rabbit”
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
rabb b it
rab b bit
ra b bbit

示例2：
输入：s = “babgbag”, t = “bag”
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 “bag” 的方案。
ba b g bag
ba bgba g
b abgb ag
ba b gb ag
babg bag

动态规划

动规五部曲

  1. 确定dp数组（dp table）以及下标的含义
    dp[i][j]：长度为[0, i - 1]的字符串s与长度为[0, j - 1]的字符串t，在s的子序列中t出现的个数

  2. 确定递推公式

    • 当s[i-1] == t[j-1]，考虑使用s[i-1]和不使用s[i-1]两种情况
      • dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    • 当s[i-1] != t[j-1]，说明当前字符不等，只能不使用s[i-1]
      • dp[i][j] = dp[i-1][j]

  3. dp数组如何初始化
    dp数组所有元素都初始化为0从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j] 是从上方和左上方推导而来，那么 dp[i][0] 和dp[0][j]是一定要初始化的。

    • dp[i][0] = 1：当t为空串时，s的任何子序列都包含空串这一种情况
    • dp[0][j] = 0：当s为空串时，t不为空串，s的子序列不可能包含t

  4. 确定遍历顺序
    从前往后遍历

  5. 举例推导dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        
        // 可以省略第一行初始化为0
        for (int j = 0; j <= t.length(); j++) {
            dp[0][j] = 0;
        }

        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()];
    }
}