115. 不同的子序列
题目描述
输入两个字符串 s 和 t。从 s 中删掉若干字符（也可以不删），剩下的字符保持原有次序，得到的就是 s 的一个子序列。
统计有多少种选取方式，使得到的子序列恰好等于 t。只要选中的下标集合不同，就算作不同的方式。
返回方式总数。数据保证答案不超过 32 位有符号整数的范围。
示例 1
输入：s = "rabbbit", t = "rabbit" 输出：3
解释：s 中有三个连续的 b，从中任选两个，共 3 种方式拼出 rabbit。
示例 2
输入：s = "babgbag", t = "bag" 输出：5
解释：按选中位置不同，共有 5 种方式从 s 中取出 bag。
数据范围
1 <= s.length, t.length <= 1000s和t只含英文字母。
解题思路：二维动态规划
设 dp[i][j] 为 s 前 i 个字符中等于 t 前 j 个字符的子序列个数。dp[i][0] = 1（空串只有一种选法）。对 s[i-1]：不用它，有 dp[i-1][j] 种；如果 s[i-1] == t[j-1]，还可以用它匹配 t[j-1]，再加 dp[i-1][j-1] 种。
为什么正确
每行只依赖上一行的正上方和左上方。
复杂度分析
时间 O(mn)，空间 O(mn)（可压缩为 O(n)）。
易错点
即使 s[i-1] == t[j-1]，也要保留“不用它”的 dp[i-1][j]，否则会漏掉用后面相同字符的选法。中间值可能很大，C++ / Java 要用更宽的类型。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = 1
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = dp[i - 1][j]
if s[i - 1] == t[j - 1]:
dp[i][j] += dp[i - 1][j - 1]
return dp[m][n]class Solution {
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
long[][] dp = new long[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j];
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] += dp[i - 1][j - 1];
}
}
}
return (int)dp[m][n];
}
}class Solution {
public:
int numDistinct(string s, string t) {
int m = s.size(), n = t.size();
vector<vector<unsigned long long>> dp(m + 1, vector<unsigned long long>(n + 1, 0));
for (int i = 0; i <= m; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j];
if (s[i - 1] == t[j - 1]) {
dp[i][j] += dp[i - 1][j - 1];
}
}
}
return (int)dp[m][n];
}
};func numDistinct(s string, t string) int {
m, n := len(s), len(t)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := 0; i <= m; i++ {
dp[i][0] = 1
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
dp[i][j] = dp[i-1][j]
if s[i-1] == t[j-1] {
dp[i][j] += dp[i-1][j-1]
}
}
}
return dp[m][n]
}var numDistinct = function(s, t) {
const m = s.length, n = t.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) {
dp[i][0] = 1;
}
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j];
if (s[i - 1] === t[j - 1]) {
dp[i][j] += dp[i - 1][j - 1];
}
}
}
return dp[m][n];
};function numDistinct(s: string, t: string): number {
const m = s.length, n = t.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) {
dp[i][0] = 1;
}
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j];
if (s[i - 1] === t[j - 1]) {
dp[i][j] += dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}其他解法
两种解法的状态转移完全相同；二维表更直观，一维滚动数组把空间压到 O(n)。
解法 2：一维滚动数组 时间 O(m·n)，空间 O(n)
dp[j] 表示当前已扫描的 s 前缀中，子序列等于 t 前 j 个字符的方案数，dp[0] = 1。每读入 s 的一个字符 ch，让 j 从 n 倒序到 1；若 ch == t[j-1]，则 dp[j] += dp[j-1]。倒序保证 dp[j-1] 仍是上一行的值。
二维状态表压缩成一行，空间从 O(m·n) 降到 O(n)。代价是丢失中间状态，必须理解为什么要倒序更新。
class Solution:
def numDistinct(self, s: str, t: str) -> int:
n = len(t)
dp = [0] * (n + 1)
dp[0] = 1
for ch in s:
for j in range(n, 0, -1):
if ch == t[j - 1]:
dp[j] += dp[j - 1]
return dp[n]class Solution {
public int numDistinct(String s, String t) {
int n = t.length();
long[] dp = new long[n + 1];
dp[0] = 1;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
for (int j = n; j >= 1; j--) {
if (ch == t.charAt(j - 1)) dp[j] += dp[j - 1];
}
}
return (int)dp[n];
}
}class Solution {
public:
int numDistinct(string s, string t) {
int n = t.size();
vector<unsigned long long> dp(n + 1, 0);
dp[0] = 1;
for (char ch : s) {
for (int j = n; j >= 1; j--) {
if (ch == t[j - 1]) dp[j] += dp[j - 1];
}
}
return (int)dp[n];
}
};func numDistinct(s string, t string) int {
n := len(t)
dp := make([]int, n+1)
dp[0] = 1
for i := 0; i < len(s); i++ {
for j := n; j >= 1; j-- {
if s[i] == t[j-1] {
dp[j] += dp[j-1]
}
}
}
return dp[n]
}var numDistinct = function(s, t) {
const n = t.length;
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
for (const ch of s) {
for (let j = n; j >= 1; j--) {
if (ch === t[j - 1]) dp[j] += dp[j - 1];
}
}
return dp[n];
};function numDistinct(s: string, t: string): number {
const n = t.length;
const dp: number[] = new Array(n + 1).fill(0);
dp[0] = 1;
for (const ch of s) {
for (let j = n; j >= 1; j--) {
if (ch === t[j - 1]) dp[j] += dp[j - 1];
}
}
return dp[n];
}