算法讲解068 必备 见识更多二维动态规划题目

来源：算法讲解068【必备】见识更多二维动态规划题目　·　2026-11-03

依据：视频字幕 2000 字

一句话概括

用「两个前缀长度」作状态定义二维 DP：dp[i][j] = S 的前 i 个字符的子序列中，恰好等于 T 的前 j 个字符的个数；按「S 末尾字符选不选」分类转移。

它解决什么问题

给定字符串 S、T，统计 S 的子序列（不要求连续，保持相对顺序，可要可不要）中有多少个字面值严格等于 T。典型题：LeetCode 115 不同子序列（Distinct Subsequences）。

基础知识（前置概念，用大白话解释）

• 子序列（subsequence）：从原串从左往右挑若干个字符，保持相对次序，不要求连续。长度 n 的串共有 2^n 个子序列（含空串）。
• 前缀（prefix）：前 i 个字符组成的串，记作 S[0..i-1]。
• 二维 DP（2D dynamic programming）：状态由两个整数 (i, j) 决定，转移只依赖更小的 i 或 j。本题两个可变参数就是「S 取多长」「T 取多长」。
• 计数型 DP：答案是方案数，转移用加法；注意取模（本题答案在 32 位内，但竞赛里通常要 long long 或取模，见易错点）。

原理（为什么这么做是对的，尽量给直觉）

定义 dp[i][j]：只用 S 的前 i 个字符（下标 0..i-1）生成子序列，其中字面值等于 T 的前 j 个字符（下标 0..j-1）的个数。

按 S 的第 i 个字符（下标 i-1）选不选分类，这是不重不漏的划分：

1. 不选 S[i-1]：那这个子序列完全来自 S 的前 i-1 个字符，方案数 = dp[i-1][j]。
2. 选 S[i-1]：只有当 S[i-1] == T[j-1] 时才可能。此时它必须去匹配 T 的最后一个字符 T[j-1]，前面部分就是「S 前 i-1 个字符凑出 T 前 j-1 个字符」，方案数 = dp[i-1][j-1]。

两类互斥（选/不选），所以相加。这就是全部转移。

边界直觉：

• dp[i][0] = 1：T 是空串，S 的任意前缀只有「全不选」这一个子序列等于空串。
• dp[0][j] = 0（j ≥ 1）：S 是空串，凑不出非空 T。
• 注意 dp[0][0] = 1（空串等于空串，一种方案），它被 dp[i][0]=1 这一行覆盖。

为什么答案在 dp[n][m]：n = |S|、m = |T|，正好是「S 全部字符」对「T 全部字符」，就是原问题。

步骤（编号，可照着写）

1. 读入 S、T，n = |S|，m = |T|。
2. 开 (n+1) × (m+1) 的表，全部初始化为 0。
3. 对 i = 0..n：dp[i][0] = 1。
4. 对 i = 1..n：

- 对 j = 1..m：

- dp[i][j] = dp[i-1][j]（不选 S[i-1]）

- 若 S[i-1] == T[j-1]：dp[i][j] += dp[i-1][j-1]

1. 返回 dp[n][m]。

（可滚动数组优化到一维，见「竞赛模板」和「拓展」。）

样例（一个具体小例子，带每步变化）

S = "rabbbit"，T = "rabbit"，n = 7，m = 6。答案应为 3（三个 b 里选两个）。

只列关键行（行 = S 前缀长度 i，列 = T 前缀长度 j，j 从 0 到 6）：

i=0 (空):   1 0 0 0 0 0 0
i=1 'r':    1 1 0 0 0 0 0
i=2 'a':    1 1 1 0 0 0 0
i=3 'b':    1 1 1 1 0 0 0
i=4 'b':    1 1 1 2 1 0 0
i=5 'b':    1 1 1 3 3 0 0
i=6 'i':    1 1 1 3 3 3 0
i=7 't':    1 1 1 3 3 3 3

看 i=4 行 j=3：dp[4][3] = dp[3][3] + dp[3][2]（S[3]='b'==T[2]='b'）= 1 + 1 = 2，即 "rab" 有两个 b 可选。i=5 行 j=3 同理累加到 3。最终 dp[7][6] = 3。

代码（Python 一份：好读、用于理解；C++ 一份：竞赛风，能直接抄进比赛，带注释，不用玄学宏）

Python（好读版）：

def num_distinct(s: str, t: str) -> int:
    n, m = len(s), len(t)
    # dp[i][j]: s 前 i 个字符的子序列中等于 t 前 j 个字符的个数
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1
    for i in range(1, n + 1):
        for j in range(1, m + 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[n][m]

C++（竞赛风，滚动数组，直接抄）：

#include <bits/stdc++.h>
using namespace std;

// 统计 s 的子序列中等于 t 的个数（不取模，答案可能很大，用 long long）
long long numDistinct(const string& s, const string& t) {
    int n = (int)s.size(), m = (int)t.size();
    if (m > n) return 0;
    vector<long long> dp(m + 1, 0);
    dp[0] = 1;                       // 空 T 只有一种方案
    for (int i = 1; i <= n; ++i) {
        // 关键：j 必须从大到小，否则 dp[j-1] 已被本行更新，变成"可重复用 S[i-1]"
        for (int j = m; j >= 1; --j) {
            if (s[i - 1] == t[j - 1]) {
                dp[j] += dp[j - 1];
            }
            // 不相等时 dp[j] 保持不变，等价于 dp[i][j] = dp[i-1][j]
        }
    }
    return dp[m];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    cin >> s >> t;
    cout << numDistinct(s, t) << '\n';
    return 0;
}

复杂度（时间/空间，最好/平均/最坏，顺带说常数大不大）

• 时间：O(n·m)，与数据无关，最好=最坏=平均。n、m ≤ 1000 时约 1e6 次操作，极快。
• 空间：二维 O(n·m)；滚动数组 O(m)。
• 常数：极小，内层只有一个比较和一个加法，分支预测友好。1e6 规模远低于 1e8 的常规上限。

竞赛里什么时候用（看到什么题面特征就该想到它）

• 「统计 S 的子序列中有多少个等于 T / 匹配模式串」——两个串、一个当源一个当目标。
• 题面出现「子序列」「不改变相对顺序」「计数」「两个字符串长度都 ≤ 1000~2000」。
• 两个串做匹配/编辑/对齐类问题（编辑距离、最长公共子序列、通配符匹配）都是同款「双前缀」状态，看到两个串就该先想 dp[i][j] 前缀定义。
• 数据规模 n·m ≤ 1e7 左右都可直接上二维 DP。

竞赛模板（C++，可直接背下来的写法；变量名清楚）

// 计数型二维 DP 通用骨架：dp[i][j] 依赖 dp[i-1][j] 和 dp[i-1][j-1]
// 滚动数组时 j 逆序；若依赖 dp[i][j-1]（同行左侧）则 j 必须正序。
long long countSubseqEqual(const string& s, const string& t) {
    int n = (int)s.size(), m = (int)t.size();
    if (m > n) return 0;
    vector<long long> dp(m + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = m; j >= 1; --j)
            if (s[i - 1] == t[j - 1])
                dp[j] += dp[j - 1];
    return dp[m];
}

边界与易错点（WA 的常见原因，越具体越好）

1. 滚动数组方向写反：本转移依赖 dp[i-1][j-1]，一维化后 j 必须从 m 到 1 逆序。正序会让 dp[j-1] 变成「本行已更新值」，等于允许同一个 S 字符被用多次，答案偏大。
2. dp[i][0] 忘记置 1：T 为空串时答案是 1（全不选），漏了整列错。
3. 下标混淆：dp 的 i、j 是长度（1..n），s[i-1]、t[j-1] 才是字符。写成 s[i] 会越界或错位。
4. m > n 直接返回 0：S 比 T 短不可能凑出，提前剪枝也防越界。
5. 溢出：不取模时答案可达 C(n, m) 级别，n=1000 时远超 int，必须 long long；若题目要求取模（如 1e9+7），每步加法后取模，别只在最后取。
6. 多测不清空：滚动数组每轮重新 vector<long long> dp(m+1, 0) 或手动 fill，别复用脏数据。
7. 空串输入：S 或 T 为空要能正常返回（T 空返回 1，S 空且 T 非空返回 0），读入用 cin >> 时注意空行。

同类题 / 变形（说清楚怎么改）

• 编辑距离（Edit Distance）：同样 dp[i][j] 前缀定义，转移改成「删/插/换」三种取 min，相等时 dp[i][j]=dp[i-1][j-1]。
• 最长公共子序列（LCS）：相等时 dp[i-1][j-1]+1，否则 max(dp[i-1][j], dp[i][j-1])——注意这里依赖同行左侧，滚动数组要正序。
• 通配符匹配 / 正则匹配：状态同为双前缀，转移按 *、? 分类。
• 本题取模版：每步 dp[j] = (dp[j] + dp[j-1]) % MOD。
• 求具体是哪些子序列：DP 表保留后从 dp[n][m] 回溯，按「选/不选」分支走。

常见坑

• 把「子序列」当成「子串」：子串要求连续，这题不要求，别用 KMP/哈希那套。
• 滚动数组和「同行依赖」混用：LCS 要正序、本题要逆序，背模板时记清楚依赖的是 dp[i-1][*] 还是 dp[i][j-1]。
• 用 int 存答案不取模，n 稍大就爆。
• 多测时忘记重置 dp[0]=1 之外的元素。

拓展（变体、实际用途、面试常问）

• 面试高频：LeetCode 115 原题，面试官常追问「空间能否 O(m)」「如果 S 很长 T 很短怎么优化」——答滚动数组 + 提前 m>n 剪枝。
• 实际用途：生物信息学里统计 DNA 序列中某模式作为子序列出现的次数；文本挖掘里模糊匹配计数。
• 变体：允许字符替换/通配（把相等判断改成集合判断）；统计「至少包含 T 一次」可用总子序列数减去不含 T 的（容斥）。
• 与上节课（递归→DP）的关系：本题也可从递归 f(i,j) 记忆化入手，再改写成迭代；两种写法等价，比赛里直接写迭代更快。

自测 3 题（题目 + 折叠答案）

题 1：S = "babgbag"，T = "bag"，答案是多少？

const long long MOD = 1000000007;
for (int j = m; j >= 1; --j)
    if (s[i-1] == t[j-1])
        dp[j] = (dp[j] + dp[j-1]) % MOD;