#yyds干货盘点# LeetCode程序员面试金典：不同的子序列

题目：

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

题目数据保证答案符合要求 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

代码实现：

class Solution {    public int numDistinct(String s, String t) {        int m = s.length(), n = t.length();        if (m < n) {            return 0;        }        int[][] dp = new int[m + 1][n + 1];        for (int i = 0; i <= m; i++) {            dp[i][n] = 1;        }        for (int i = m - 1; i >= 0; i--) {            char sChar = s.charAt(i);            for (int j = n - 1; j >= 0; j--) {                char tChar = t.charAt(j);                if (sChar == tChar) {                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];                } else {                    dp[i][j] = dp[i + 1][j];                }            }        }        return dp[0][0];    }}