LeetCode 115. 不同的子序列

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
2. 解法二：动态规划（空间优化）
相似题目

题目描述

✅ 115. 不同的子序列

思路分析

解法一：动态规划（推荐）

核心思路：

定义 dp[i][j] 表示 s 的前 i 个字符中，t 的前 j 个字符作为子序列出现的个数。

当 s[i-1] == t[j-1] 时，s[i-1] 既可以选（与 t[j-1] 匹配），也可以不选：

选：问题规模缩减为 dp[i-1][j-1]

不选：问题规模缩减为 dp[i-1][j]

因此：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

当 s[i-1] != t[j-1] 时，s[i-1] 不能与 t[j-1] 匹配，只能不选：

dp[i][j] = dp[i-1][j]

边界条件：dp[i][0] = 1（空字符串 t 是任何字符串 s 的子序列，恰好 1 种方式）；dp[0][j] = 0（j > 0 时，空字符串 s 无法匹配非空 t）。

复杂度分析：

时间复杂度：O(m × n)，其中 m 表示字符串 s 的长度，n 表示字符串 t 的长度

空间复杂度：O(m × n)，dp 数组大小为 (m+1) × (n+1)

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        // dp[i][j] 表示 s 前 i 个字符中 t 前 j 个字符作为子序列的个数
        long[][] dp = new long[m + 1][n + 1];
        // 空 t 是任意 s 前缀的子序列，恰好 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++) {
                // s[i-1] 不选，不参与匹配
                dp[i][j] = dp[i - 1][j];
                // s[i-1] 与 t[j-1] 相同时，还可以选择匹配
                if (s.charAt(i - 1) == t.charAt(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[i][j] 表示 s 前 i 个字符中 t 前 j 个字符作为子序列的个数
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		// 空 t 是任意 s 前缀的子序列，恰好 1 种
		dp[i][0] = 1
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			// s[i-1] 不选，不参与匹配
			dp[i][j] = dp[i-1][j]
			// s[i-1] 与 t[j-1] 相同时，还可以选择匹配
			if s[i-1] == t[j-1] {
				dp[i][j] += dp[i-1][j-1]
			}
		}
	}
	return dp[m][n]
}

解法二：动态规划（空间优化）

核心思路：

观察状态转移方程，dp[i][j] 只依赖 dp[i-1][j-1] 和 dp[i-1][j]，即上一行的数据。

可将二维数组压缩为一维数组 dp[j]，从右往左更新，避免本行数据覆盖上一行的 dp[j-1]。

更新顺序：j 从 n 到 1 逆序遍历，确保 dp[j-1] 使用的是上一轮（上一行）的值。

复杂度分析：

时间复杂度：O(m × n)，其中 m 表示字符串 s 的长度，n 表示字符串 t 的长度

空间复杂度：O(n)，仅使用长度为 n+1 的一维数组

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        // 压缩为一维数组，dp[j] 表示 t 前 j 个字符作为子序列的个数
        long[] dp = new long[n + 1];
        // 空 t 是任意 s 前缀的子序列，恰好 1 种
        dp[0] = 1;
        for (int i = 1; i <= m; i++) {
            // 从右往左更新，避免覆盖上一行的 dp[j-1]
            for (int j = n; j >= 1; j--) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return (int) dp[n];
    }
}

func numDistinct(s string, t string) int {
	m, n := len(s), len(t)
	// 压缩为一维数组，dp[j] 表示 t 前 j 个字符作为子序列的个数
	dp := make([]int, n+1)
	// 空 t 是任意 s 前缀的子序列，恰好 1 种
	dp[0] = 1
	for i := 1; i <= m; i++ {
		// 从右往左更新，避免覆盖上一行的 dp[j-1]
		for j := n; j >= 1; j-- {
			if s[i-1] == t[j-1] {
				dp[j] += dp[j-1]
			}
		}
	}
	return dp[n]
}

相似题目

题目	难度	考察点
72. 编辑距离	中等	动态规划、字符串
1143. 最长公共子序列	中等	动态规划、字符串
392. 判断子序列	简单	双指针、动态规划
583. 两个字符串的删除操作	中等	动态规划、字符串
712. 两个字符串的最小ASCII删除和	中等	动态规划、字符串
44. 通配符匹配	困难	动态规划、字符串
10. 正则表达式匹配	困难	动态规划、字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/13573294