LeetCode 115困难二维动态规划
不同的子序列 图解题解
这道题到底在问什么
求 s 的子序列中有多少个等于 t。
- 示例
- s="rabbbit", t="rabbit" → 3
先想最直接的笨办法
枚举所有子序列是指数级。（动画第 3 步）
最优解：一步一步想明白
- 3枚举所有子序列是指数级。
- 4dp[i][j] 表示 s 前 i 个组成 t 前 j 个的方案数；相等时可选也可不选。
- 5dp[i][0]=1 · dp[0][j>0]=0先把边界填好:第 0 列全 1(t 是空串,1 种拼法),第 0 行除角落全 0(s 是空串,拼不出非空 t)。
- 6已填到第 3 行(s=rab)一行一行填:行 i 对应 s 的第 i 个字符。看 dp[3][3]——行3=s[2]='b'、列3=t[2]='b',相等,后面这种相等格要走『选/不选』两路相加。(动画画的是完整二维表帮理解;代码里用一维 dp[] 滚动复用每一行省内存,递推一模一样。)
- 7s[3]='b' == t[2]='b' → 1+1=2dp[4][3]:行4=s[3]='b'、列3=t[2]='b' 相等。两条路相加:不选这个 b(继承上面 dp[3][3]=1)+ 用这个 b 配掉 t 的 b(左上 dp[3][2]=1)= 2。
- 8s[5]='i' != t[3]='b' → =3dp[6][4]:行6=s[5]='i'、列4=t[3]='b' 不等。当前字符配不上,只能不选它,直接继承上一行 dp[5][4]=3。
- 9dp[7][6] = 3填到右下角 dp[7][6]=3:rabbbit 里抠出 rabbit 有 3 种方式——三个 b 任选一个去配 t 里的那个 b。
- 12一句话记住：dp[i][j] 表示 s 前 i 个组成 t 前 j 个的方案数；相等时可选也可不选。
- 15O(m·n) 填表, 非指数枚举核心:暴力枚举所有子序列是指数级;DP 把『每个前缀配每个前缀』的方案数存进 m×n 的表,每格 O(1) 推出,整体 O(m·n)。三个 b 的贡献沿 b 列累加成最终的 3。
- 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=dp 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
⚠️ 容易写错的地方
✗ 错：只照着眼前元素做局部判断
✓ 对：维护动画里的完整状态
本题的答案由状态转移决定，少一个状态就会漏情况。
✗ 错：边界输入不单独跑
✓ 对：先跑空/单元素/重复/极端值
这些输入最容易暴露初始化和越界问题。
完整代码（Python / C++ / Java）
Python
class Solution:
def numDistinct(self, s, t):
m, n = len(s), len(t)
dp = [0] * (n + 1)
dp[0] = 1
for ch in s:
for j in range(n - 1, -1, -1):
if ch == t[j]:
dp[j + 1] += dp[j]
return dp[n]C++
class Solution {
public:
int numDistinct(string s, string t) {
int n = t.size();
vector<unsigned long long> dp(n+1);
dp[0] = 1;
for (char ch : s) {
for (int j=n-1;j>=0;j--) if (ch == t[j]) dp[j+1] += dp[j];
}
return (int)dp[n];
}
};Java
class Solution {
public int numDistinct(String s, String t) {
int n = t.length();
long[] dp = new long[n+1];
dp[0] = 1;
for (char ch : s.toCharArray()) {
for (int j=n-1;j>=0;j--) if (ch == t.charAt(j)) dp[j+1] += dp[j];
}
return (int) dp[n];
}
}套路模板 · 不同的子序列迁移骨架
# 1. 定义状态
state = init()
# 2. 按顺序读输入
for x in data:
update(state, x) # 只做本题允许的安全转移
# 3. 从状态里取答案
return answer(state)// 1. init state
for (auto x : data) {
// update state with the same invariant
}
return ans;// 1. init state
for (int x : data) {
// update state with the same invariant
}
return ans;复杂度
时间复杂度
O(m·n)
m=len(s)、n=len(t);填满 m×n 的 dp 表,每格 O(1)
空间复杂度
O(n)
代码就是一维滚动数组 dp[n+1],只存一行,空间 O(n);二维表才是 O(m·n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 不同的子序列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心状态是什么？+
dp[i][j] 表示 s 前 i 个组成 t 前 j 个的方案数；相等时可选也可不选。
这道题为什么用「二维动态规划」，换最直接的暴力解会差在哪？+
二维动态规划抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。