ch10 动态规划：二维DP

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] 都不选的情况；同理，不选 b[j] 的情况中也包含了 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 会学习到。

部分题目解法

编辑距离

• 状态定义 dp[i][j] 表示把 【a 的前 i 项】 修改成【b 的前 j 项】需要的最少操作次数。
• 状态转移，3 种选择决策取最小值：
  1. 把 a 的前 i - 1 位转换为 b 的前 j - 1 位，然后把 a 的第 i 位修改成 b 的第 j 位
     • a[i] != b[j] 时才需要修改，对应 dp[i-1][j-1] + (a[i] != b[j])
  2. 把 a 的前 i - 1 位转换为 b 的前 j 位，然后把 a 的第 i 位删除，对应 dp[i-1][j] + 1
  3. 把 a 的前 i 位转换为 b 的前 j - 1 位，然后在 a 后面插入一个 b[j]，对应 dp[i][j-1] + 1
• 边界：dp[i][0] = i，dp[0][j] = j

方格取数

• 状态定义： dp[x1][y1][x2][y2] 表示第一条路走到 (x1, y1)，第二条路走到 (x2, y2) 的最大取数之和。

  • 实际上只关心两条路走相同步数时的状态，走相同步数才有可能在两条路径末尾遇到一起，遇到一起才受到“方格中的数只能取一次”的限制。根据这个观察，可以排除一个冗余维度，dp 数组用三维即可。
  • dp[i][x1][x2]：两条路都走了 i 步，第一条路到达第 x1 行，第二条路到达第 x2 行时的最大取数之和。
  • 记此时第一条路到达 y1 列，第二条路到达 y2 列。
  • 因为起点是 (1, 1) ，有 (x1 - 1) + (y1 - 1) = i，则 y1 = i + 2 - x1，因此第一条路的列数可以计算得到，不用作为 dp 的维度。同理 y2 = i + 2 - x2 。

• 状态转移：

  • 列举两条路径上一步分别可能在哪里，有 4 种情况，决策取最大值。
  • 再加上 (x1, y1) 和 (x2, y2) 位置上的值，如果是同一个位置，则只能加一次。

• 边界：走 0 步时在起点，取到起点的数，dp[0][1][1] = a[1][1] 。

• 参考代码

  const int N = 10;int dp[N*2][N][N], a[N][N];int main() {int n, x, y, w;cin >> n;while (cin >> x >> y >> w) {a[x][y] = w;}dp[0][1][1] = a[1][1];for (int i = 1; i <= 2 * (n - 1); i++) {for (int x1 = 1; x1 <= n; x1++) {for (int x2 = 1; x2 <= n; x2++) {int y1 = i + 2 - x1, y2 = i + 2 - x2;if (y1 < 1 || y1 > n || y2 < 1 || y2 > n) continue; //位置非法dp[i][x1][x2] = max({dp[i-1][x1-1][x2-1], dp[i-1][x1-1][x2], dp[i-1][x1][x2-1], dp[i-1][x1][x2]}) + a[x1][y1];if (x1 != x2) dp[i][x1][x2] += a[x2][y2];}}}// 思考输出什么return 0;}

传纸条

• 本题要找两条起点到终点的路径（从终点到起点，与从起点到终点是一样的），使得经过的位置数字之和最大。
• 与“方格取数”的区别在于，“方格取数”允许两条路径有相交（允许同一个位置被两条路径走过），本题要求两条路径不能相交。
• 考虑放宽本题限制，也允许路径相交，会不会影响答案。
  • 相交的时候令路径绕一下不要相交，能取到更多数字，所以允许相交不会令答案更优。
  • 也不会导致答案更劣，因为是放宽了限制。
  • 所以允许路径相交不影响结果，
  • 本题转换为“方格取数”问题，解法相同。改输入形式，用到列数的地方注意是 m 列不是 n 列，根据数据范围，dp 数组开大一些。

传球游戏

• 状态定义：dp[i][j] 表示球传了 i 次到 j 号位置的方案数。
• 状态转移：
  • 对于 dp[i][j]，考虑前一步的位置，可以从左边 L = j - 1 的位置传到 j，也可以从右边 R = j + 1 的位置传到 j 。注意 L 和 R 越界时怎么修改，对应的是环上的哪个位置。
  • dp[i][j] = dp[i-1][L] + dp[i-1][R]
• 边界：传了 0 次在起点有 1 种方案，在其他位置有 0 种方案。
  • 哪个位置作为起点都可以，可假设 1 号位置是起点 (dp[0][1] = 1)；需注意答案，答案为传回起点的方案。

数列分段 III

• 状态定义：dp[i][j] 表示前 i 个数字恰好分为 j 段的最小代价。
• 状态转移：
  • 与之前的数列分段问题类似，枚举 p，表示前 p 个数字分为 j - 1段（代价 dp[p][j-1]），第 p+1 ~ i 个数字作为最后一段。
  • 预处理 a[] 数组的前缀和，可以快速计算最后一段的代价。
  • 取最小的 (dp[p][j-1] + 最后一段代价) 为 dp[i][j] 的值。
• 边界：
  • 0 个数字分为 0 段代价为 0，dp[0][0] = 0。
  • i < j 时，无法分段，用一个极大值来表示无法分段。
  • dp[i][j] 的计算中要取 min，dp[i][j] 也要赋一个极大的初始值，可以最初先把整个 dp 数组赋值为极大值。

乌龟棋

• 状态定义：dp[i][j][p][q] 表示用了 i 张 1，j 张 2，p 张 3，q 张 4 后的最大分数。
• 状态转移：
  • 考虑最后一次用的是哪一张，有 4 种情况，比如用了标有数字 1 的，对应的就是 dp[i-1][j][p][q] 。（注意当 i 是 0 时，注意 dp[i-1][j][p][q] 数组越界，不用考虑。j = 0, p = 0, q = 0 的情况同理）
  • 4 种情况决策取 max。
  • 用了这些卡片后，到达的位置是 i+j*2+p*3+q*4+1，获得 a[i+j*2+p*3+q*4+1] 分，加到 dp[i][j][p][q] 中。
• 边界
  • 1 张卡片都没用时，分数为 0。