网站导航
> 技术文档 > 算法 ch10 - 动态规划：二维DP

算法 ch10 - 动态规划：二维DP

网友: 技术文档 2025-08-08 07:34:17

ch10 动态规划：二维DP

二维平面上的移动问题

  • 例如算法基础“递推”的“路径计数”问题，本节课的“Number Triangles”、“过河卒”。

  • 通常用 dp[i][j] 表示走到第 i 行第 j 列的…

  • 例题：Number Triangles

    • dp[i][j]：从起点（左上角）走到第 i 行第 j 列的最大数字之和

    • 状态转移

      • 可以上面 (i - 1, j) 或左边 (i, j - 1) 走到 (i, j)，从两个选择中决策取最大值，再加上 (i, j) 位置上的值。
      • dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][j]

    • 边界：

      • 数据是个三角形，第 i 行只有 i 列，满足 j <= i 的位置 (i, j) 才是合法位置。
      • 可将不合法位置作为边界，走到不合法位置的方案数为 0 。即对于所有的 j > i，dp[i][j] = 0。

    • 代码：

      const int N = 1010;int a[N][N], dp[N][N];int main() {int n;cin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {cin >> a[i][j];dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][j];}}// 目标是走到第n行，取dp[n][1~n]的最大值为答案return 0;}

两个序列相关问题

  • 例如最长公共子序列（LCS）问题，“编辑距离”问题。

  • 通常用 dp[i][j] 表示 a 序列前 i 项、b 序列前 j 项的…

  • 例题：最长公共子序列

    • dp[i][j]：a 的前 i 项与 b 的前 j 项的最长公共子序列长度。

    • 状态转移：考虑子序列中选不选 a[i]、b[j]

      • 不选 a[i]，相当于在 a 的前 i - 1 项中选，dp[i-1][j]
      • 不选 b[j]，相当于在 b 的前 j - 1 项中选，dp[i][j-1]
      • 当 a[i] == b[j] 时，可以选它作为子序列的最后一项，先在 a 的前 i - 1 项和 b 的前 j - 1 项中选出最长的子序列，再加上最后这一个，dp[i-1][j-1] + 1
      • 以上三种选择中取最大值为 dp[i][j] 的值
      • 为什么不用考虑 a[i] 和 b[j] 都不选，dp[i-1][j-1] ？
        • 不选 a[i] 的情况就包含了 a[i] 和 b[j] 都不选了
        • 或者换个角度思考，dp[i-1][j-1] 不可能大于 dp[i-1][j] 或 dp[i-1][j]，所以不用考虑

    • 边界：

      • 当 i 是 1 时，要用到 dp[0][]，当 j 是 1 时，要用到 dp[][0] ，将 dp 数组第 0 行和第 0 列作为边界。
      • dp[0][] 是在 a 的前 0 项中选（空），dp[0][0~n] = 0，同理 dp[0~n][0] = 0

    • 代码

      int main() { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> b[i]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); if (a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1); } } cout << dp[n][n] << \'\\n\'; return 0;}

  • 例题：公共子序列计数

    • dp[i][j]：在 a 的前 i 项和 b 的前 j 项中有多少对公共子序列。

    • 状态转移，分为四类情况

      1. 不选 a[i]，dp[i-1][j]
      2. 不选 b[j]，dp[i][j-1]
      3. a[i] 和 b[j] 都不选，dp[i-1][j-1] ，但第 1、2 类中都包含了这一类情况，所以这类情况反而是被多算了一次，要减掉（这里也称为容斥原理，先包容进来，多算的再排斥出去）。
      4. 如果 a[i] == b[j]，选 a[i]、b[j]，dp[i-1][j-1]
      • 前 3 类：dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
      • 第 4 类：if (a[i] == b[j]) dp[i][j] += dp[i-1][j-1];

    • 边界：

      • 根据以上递推式，计算 dp[1][] 要用到 dp[0][]，计算 dp[][1] 要用到 dp[][0] 。
      • 根据题意，空序列也算，所以 dp[0][0~m] = 1，dp[1~n][0] = 1。

拓展：组合数学中的分组分配问题

  • 问题模型：将 n 个物品分为 k 组，有多少种不同方案。

  • 根据物品有无区别，组有无区别，是不同的组合计数问题。

    1. 物品之间无区别，组之间有区别

      • 例如将 n 个三好学生名额分配给 k 个班级，有多少种分法。三好学生名额是无区别的，班级是有区别的。
      • 每个组至少分一个物品：“隔板法”解决即可，Cn−1k−1C_{n-1}^{k-1}Cn−1k−1​。
      • 允许有的组为空：先多送 k 个物品去分，有 Cn+k−1k−1C_{n+k-1}^{k-1}Cn+k−1k−1​ 种分法，分完了每个组各回收一个物品，就有的组为空了。

    2. 物品之间无区别，组之间无区别

      • 例如本节课“数的划分”这道题，将整数 n 看作 n 个物品，要分成 k 组。

      • 组之间无区别即不考虑整数划分的大小顺序了，1, 2 和 2, 1 看作同一种，所以分组时要固定一个顺序（例如从大到小），避免重复统计。

      • 每组至少一个物品

        • dp[i][j]：将 i 个物品分为 j 组的方案数（限制第 1~j 组的物品数量从大到小，每组不能为空）

        • 状态转移

          • 因为物品数量是从大到小的顺序，分为最后一组的物品数量 == 1 和 > 1 两类情况
          1. 最后一组（第 j 组）分 1 个物品：那么另外 i - 1 个物品分在前 j - 1 组中，dp[i-1][j-1]
          2. 最后一组的物品数量 > 1 个：先将 i - j 个物品分这 j 组中，dp[i-j][j] （此时最后一组有 >= 1 个物品），再将剩余的 j 个物品分在这 j 组中（每组各一个，此时最后一组有 > 1 个物品。因为每组都 + 1，可以保证第 1~j 组的物品数量仍然是从大到小的）。
          • 所以 dp[i][j] = dp[i-1][j-1] + dp[i-j][j]

        • 边界：dp[1][1] = 1

        • 例题“数的划分”代码：

          const int N = 210;int dp[N][7];int main() {int n, k;cin >> n >> k;dp[1][1] = 1;for (int i = 2; i <= n; i++) { // i个物品最多只能分i组，所以j<=i,j<=kfor (int j = 1; j <= min(i, k); j++) {dp[i][j] = dp[i-1][j-1] + dp[i-j][j];}}cout << dp[n][k] << \'\\n\';return 0;}

      • 允许有的组没有物品

        • dp[i][j]：将 i 个物品分为 j 组的方案数（限制第 1~j 组的物品数量从大到小，允许有的组为空）
        • 状态转移：同理，分为最后一组的物品数量 == 0 和 > 0 两种情况
          • dp[i][j] = dp[i][j-1] + dp[i-j][j]

    3. “物品之间有区别，组之间无区别”和“物品之间有区别，组之间有区别”，涉及到“第二类斯特林数”，算法 2 会学习到。

网络标签：

相关问题