LeetCode 115 & 392：不同子序列 / 判断子序列

LeetCode 115 & 392：不同子序列 / 判断子序列 —— 联合题解 ✅

这两道题 名字像、状态像、但 DP 含义完全不同。

📌 题目列表

📖 内容概要

给定字符串 s 和 t：

• 392：判断 s 是否是 t 的子序列
• 115：统计 t 在 s 中作为子序列出现的次数

✅ 动态规划 ✅ 子序列问题 ✅ 面试高频

💡 统一 DP 定义

dp[i][j] =
s 的前 i 个字符
与 t 的前 j 个字符
的某种关系

🔁 状态转移对比（核心）

✅ 115 只用上一行（i-1） ✅ 392 只用当前行（i）

✅ 392 题：判断子序列（判定）

思路

• 匹配成功 → 同时前进
• 不匹配 → 只前进 t

AC 代码（Java）

class Solution {
public boolean isSubsequence(String s, String t) {
char[] ss = s.toCharArray();
char[] tt = t.toCharArray();
int len1 = s.length();
int len2 = t.length();
int[][] dp = new int[len1 + 1][len2 + 1];

for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (ss[i – 1] == tt[j – 1]) {
dp[i][j] = dp[i – 1][j – 1] + 1;
} else {
dp[i][j] = dp[i][j – 1];
}
}
}
return dp[len1][len2] == len1;
}
}

✅ 为什么没有 dp[i-1][j]

• 不能跳过 s
• 只能跳过 t

✅ 115 题：不同子序列（计数）

思路

• 匹配成功：
  • 用当前字符
  • 不用当前字符
• 匹配失败：
  • 只能不用当前字符

AC 代码（Java）

class Solution {
public int numDistinct(String s, String t) {
char[] ss = s.toCharArray();
char[] tt = t.toCharArray();
int len1 = s.length();
int len2 = t.length();
int[][] dp = new int[len1 + 1][len2 + 1];

// 初始化
for (int i = 0; i <= len1; i++) {
dp[i][0] = 1;
}

for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (ss[i – 1] == tt[j – 1]) {
dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j];
} else {
dp[i][j] = dp[i – 1][j];
}
}
}
return dp[len1][len2];
}
}

🔍 两题核心差异总结（必背）

⏱️ 复杂度分析

✅ 一句话总结

392 是在“找一条路”，115 是在“数所有路”。

📌 面试加分点（建议记住）

• ✅ 为什么 115 不用 dp[i][j-1]？
• ✅ 为什么 392 不用 dp[i-1][j]？
• ✅ 初始化为什么 dp[i][0] = 1？
• ✅ 如何用滚动数组优化空间？