算法讲解067 必备 从递归入手二维动态规划

来源：算法讲解067【必备】从递归入手二维动态规划　·　2026-11-01
依据：无字幕，部分内容由我补充（已标注）

一句话概括

二维动态规划（2D DP）就是状态由两个维度（通常是位置/长度/两个序列的下标）确定的 DP，从递归暴力搜索出发，加记忆化（memoization）消除重复子问题，再改写成自底向上的填表；核心是状态定义 + 转移方程 + 边界 + 遍历顺序四件事。

它解决什么问题

共同特征：答案依赖两个独立变化的量，且大问题由小问题组合而来。

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

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

为什么记忆化是对的：递归暴力会重复计算同一子问题（比如 LCS 里 (i,j) 会被多条路径到达）。子问题的答案只由 (i,j) 决定，与"怎么到达这里"无关——这叫无后效性。所以第一次算完存起来，之后直接查表，正确性不变，复杂度从指数降到"状态数 × 单状态转移代价"。

为什么自底向上是对的：把状态看成有向无环图（DAG），边是"大状态依赖小状态"。只要按拓扑序填表，填每个格子时依赖的格子都已就绪，结果与记忆化完全一致。二维 DP 里"拓扑序"通常就是按 i 递增、j 递增（或按区间长度递增）。

为什么二维：因为问题有两个自由维度。比如 LCS 中"s1 处理到哪"和"s2 处理到哪"互相独立，必须同时记录，否则信息丢失。

直觉模板：dp[i][j] = 若干 dp[i-1][j-1] / dp[i-1][j] / dp[i][j-1] 的组合，边界是 i=0 或 j=0 那一行/列。

步骤（编号，可照着写）

  1. 写暴力递归：明确函数签名 f(i, j) 的含义（一句话），写出终止条件和所有分支的 return。
  2. 找重复子问题：确认 f(i,j) 会被多次调用（画递归树或数状态数）。
  3. 加记忆化：开 memo[i][j]，初值设为"未计算"哨兵（如 -1 或 INF），进入函数先查表。
  4. 确定状态范围：i ∈ [0, n]、j ∈ [0, m]，据此定数组大小（多开 1~2 格防越界）。
  5. 改自底向上：把 f(i,j) 的 return 改写成 dp[i][j] = ...，按依赖方向定遍历顺序，先填边界。
  6. 验证小样例：手推 3×3 表，和递归结果对拍。
  7. 空间压缩（可选）：若只依赖上一行，压成两行/一行；注意压缩后遍历方向（01 背包要倒序）。
  8. 多测清空：每组数据前 fill 或重新 assign，别用 memset 对 vector<vector<long long>> 乱搞。

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

最长公共子序列（LCS）：s1 = "abcde"，s2 = "ace"，答案 3（"ace"）。

状态：dp[i][j] = s1 前 i 个字符与 s2 前 j 个字符的 LCS 长度。

转移：

边界：dp[0][*] = dp[*][0] = 0。

填表（行 = i，列 = j，s2 = "ace"）：

| i\j | 0 | 1(a) | 2(c) | 3(e) |

|---|---|---|---|---|

| 0 | 0 | 0 | 0 | 0 |

| 1(a) | 0 | 1 | 1 | 1 |

| 2(b) | 0 | 1 | 1 | 1 |

| 3(c) | 0 | 1 | 2 | 2 |

| 4(d) | 0 | 1 | 2 | 2 |

| 5(e) | 0 | 1 | 2 | 3 |

每步变化：(1,1) 字符 a==a → dp[0][0]+1=1；(2,2) 字符 b≠c → max(dp[1][2], dp[2][1]) = max(1,1)=1；(3,3) 字符 c==c → dp[2][2]+1=2；(5,3) 字符 e==e → dp[4][2]+1=3。答案 dp[5][3]=3。

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

Python（记忆化递归，好读）

import sys
from functools import lru_cache

def lcs(s1: str, s2: str) -> int:
    n, m = len(s1), len(s2)
    @lru_cache(maxsize=None)
    def f(i: int, j: int) -> int:
        # s1 前 i 个字符 与 s2 前 j 个字符 的 LCS 长度
        if i == 0 or j == 0:
            return 0
        if s1[i - 1] == s2[j - 1]:
            return f(i - 1, j - 1) + 1
        return max(f(i - 1, j), f(i, j - 1))
    return f(n, m)

if __name__ == "__main__":
    print(lcs("abcde", "ace"))  # 3

Python（自底向上，用于对照）

def lcs_dp(s1: str, s2: str) -> int:
    n, m = len(s1), len(s2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

C++（竞赛风，可直接抄）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s1, s2;
    cin >> s1 >> s2;
    int n = (int)s1.size(), m = (int)s2.size();

    // dp[i][j] = s1 前 i 个字符 与 s2 前 j 个字符 的 LCS 长度
    // 用 vector，多测时重新 assign 即可，避免 memset 对 vector 的坑
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << dp[n][m] << '\n';
    return 0;
}

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

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

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

模板 1：通用二维 DP 骨架（以 LCS 为例，含滚动数组版）

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

// 二维 DP 通用骨架：先写递归 -> 记忆化 -> 填表
// 这里给 LCS 的滚动数组版，空间 O(min(n,m))
int lcs(const string& s1, const string& s2) {
    int n = (int)s1.size(), m = (int)s2.size();
    // 让 s2 是较短的那个，滚动数组更省
    if (n < m) return lcs(s2, s1);
    vector<int> prev(m + 1, 0), cur(m + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cur[0] = 0;
        for (int j = 1; j <= m; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                cur[j] = prev[j - 1] + 1;
            } else {
                cur[j] = max(prev[j], cur[j - 1]);
            }
        }
        swap(prev, cur);
    }
    return prev[m];
}

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

模板 2：网格最小路径和（含障碍，滚动数组）

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

const int INF = 0x3f3f3f3f;

// grid[i][j] = 0 表示可走，1 表示障碍；求 (0,0)->(n-1,m-1) 最小代价
int minPathSum(vector<vector<int>>& grid) {
    int n = (int)grid.size(), m = (int)grid[0].size();
    vector<int> dp(m, INF);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 1) { dp[j] = INF; continue; }  // 障碍
            if (i == 0 && j == 0) { dp[j] = grid[i][j]; continue; }
            int fromUp   = (i > 0) ? dp[j] : INF;       // 上一行同列（未更新前是 i-1 行）
            int fromLeft = (j > 0) ? dp[j - 1] : INF;   // 本行左列（已更新）
            dp[j] = min(fromUp, fromLeft) + grid[i][j];
        }
    }
    return dp[m - 1] >= INF ? -1 : dp[m - 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n, vector<int>(m));
    for (auto& row : g) for (auto& x : row) cin >> x;
    cout << minPathSum(g) << '\n';
    return 0;
}

模板 3：区间 DP 骨架（石子合并，dp[l][r]）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n + 1), pre(n + 1, 0);
    for (int i = 1; i <= n; ++i) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; }
    // dp[l][r] = 合并区间 [l,r] 的最小代价
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
    for (int len = 2; len <= n; ++len) {          // 按区间长度递增（拓扑序）
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            dp[l][r] = INT_MAX;
            for (int k = l; k < r; ++k) {         // 枚举分割点
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
            }
            dp[l][r] += pre[r] - pre[l - 1];      // 合并代价
        }
    }
    cout << dp[1][n] << '\n';
    return 0;
}

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

  1. 下标 0/1 混用：dp[i][j] 对应 s1[i-1] 还是 s1[i]？写之前定死，全篇统一。字符串题推荐 dp 下标从 1 开始、字符串访问 s[i-1]。
  2. 数组开小：dp[n][m] 但循环到 i<=n，越界。统一开 n+1 行 m+1 列。
  3. 边界没初始化：LCS 的 dp[0][*]/dp[*][0] 必须为 0；编辑距离的 dp[i][0]=i、dp[0][j]=j 漏了必错。
  4. 遍历顺序错：依赖 dp[i-1][j-1] 却按 j 外层 i 内层填（一般也行，但滚动数组时不行）。滚动数组 + 依赖左上角时，必须保留 prev[j-1] 或临时变量，否则被覆盖。
  5. 滚动数组方向：01 背包一维压缩必须 j 从大到小；完全背包从小到大。搞反就是"物品无限用"或"只能用一次"。
  6. 多测不清空：vector 用 assign 重置；static 数组用 fill。memset 对 long long 数组只能清 0 或 -1，别清 0x3f（会得到 0x3f3f3f3f3f3f3f3f，不是 INF 的 long long 版）。
  7. int 溢出：方案数、路径数、区间代价和可能超 2^31，用 long long。取模题每步 % MOD。
  8. INF 相加溢出：dp[i-1][j] + cost 若 dp 是 INF 会溢出成负数，先判 INF 再转移，或 INF 取 0x3f3f3f3f（两倍不溢出 int）。
  9. 区间 DP 顺序：必须按 len 递增，不能按 l 递增（dp[l][r] 依赖更短区间）。
  10. 空串/空序列：n=0 或 m=0 时答案应为 0/n/m，循环不进入要保证返回正确。

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

常见坑

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

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

题 1：s1 = "intention"，s2 = "execution"，求编辑距离（插入/删除/替换代价均为 1）。

答案

答案 5。经典例子：intention → execution 需 5 步（如 intention → inention（删 t）→ enention（i→e）→ exention（n→x）→ exection（n→c）→ execution（插 u））。用 dp[i][j] 转移：s1[i-1]==s2[j-1] 取 dp[i-1][j-1]，否则 1+min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])，边界 dp[i][0]=i、dp[0][j]=j。

</details>

题 2：3×3 网格，从 (0,0) 到 (2,2)，只能向右/向下，中间 (1,1) 有障碍，求路径数。

答案

答案 2。无障碍共 C(4,2)=6 条；经过 (1,1) 的路径 = 到 (1,1) 的 2 条 × 从 (1,1) 到 (2,2) 的 2 条 = 4 条，6-4=2。DP 验证：dp[0][*]=dp[*][0]=1，dp[1][1]=0（障碍），dp[1][2]=dp[0][2]+dp[1][1]=1，dp[2][1]=1，dp[2][2]=dp[1][2]+dp[2][1]=2。

</details>

题 3：石子合并，n=4，石子数 [4,1,1,4]，每次合并相邻两堆代价为两堆之和，求合并成一堆的最小总代价。

答案

答案 18。最优：[4,1,1,4] → [4,2,4]（合并 1+1=2，代价 2）→ [6,4]（合并 4+2=6，代价 6）→ [10]（合并 6+4=10，代价 10），总代价 2+6+10=18。区间 DP：dp[l][r]=min_k(dp[l][k]+dp[k+1][r]) + sum(l..r)，按 len 从 2 到 4 填表。

</details>

竞赛补充

以下内容字幕未涉及，按竞赛需要补充：

  • 一维化寻址：大表用 vector<int> dp((n+1)*(m+1))