如何用动态规划解决走方格问题的？

很多人第一次接触动态规划，都是从“走格子”开始的：在一个二维网格上，从起点走到终点，每次只能做有限几种移动，问方案数、最小代价，或者最大收益。 第一题：最小路径和 给定一个 \(n \times m\) 的非负整数网格 \(a\)，从左上角出发走到右下角，每次只能向右或向下走一步，路径上的数字都要累加。求最小路径和。 例如下面这个 \(3 \times 3\) 的网格： \[\begin{bmatrix} 1 & 3 & 1 \\ 1 & 5 & 1 \\ 4 & 2 & 1 \end{bmatrix} \] 一种最优路径是：\( 1 \to 3 \to 1 \to 1 \to 1 \)。所以答案是 \( 1 + 3 + 1 + 1 + 1 = 7 \) 如果我们已经知道到达前面格子的最小代价，那么到达当前格子的最小代价，也就能顺手推出来。 设 \( dp[i][j] \) 表示从起点走到格子 \((i,j)\) 的最小路径和。由于每次只能向右或向下，所以到达 \((i,j)\) 的最后一步只可能来自： 上方的 \((i-1,j)\) 左侧的 \((i,j-1)\) 因此有转移方程：\( dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1]) + a[i][j] \) 这就是 DP 的核心：当前状态来自有限个前驱状态。 初始化 起点最简单： \[dp[0][0] = a[0][0] \] 第一行只能一直从左边走来，因此： \[dp[0][j] = dp[0][j-1] + a[0][j] \] 第一列只能一直从上边走来，因此： \[dp[i][0] = dp[i-1][0] + a[i][0] \] 遍历顺序 因为 \(dp[i][j]\) 依赖上方和左方，所以自然按从上到下、从左到右的顺序填表。 int main() { vector<vector<int>> a = { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }; int n = a.size(), m = a[0].size(); vector<vector<int>> dp(n, vector<int>(m, 0)); dp[0][0] = a[0][0]; for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + a[i][0]; for (int j = 1; j < m; j++) dp[0][j] = dp[0][j - 1] + a[0][j]; for (int i = 1; i < n; i++) for (int j = 1; j < m; j++) dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j]; cout << dp[n - 1][m - 1] << "\n"; } 复杂度 显然时间复杂度是 \( O(nm) \)，空间复杂度也是 \( O(nm) \) 空间优化 上一题的情境下，空间复杂度可以更低。 仔细观察转移式：\( dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1]) + a[i][j] \)。如果我们是一行一行计算，那么在处理第 \(i\) 行时： \(dp[i-1][j]\) 是“上一行同一列” \(dp[i][j-1]\) 是“当前行左边” 换句话说，计算当前行时，我们并不需要保存整个二维表，只需要保存： 上一行的信息 当前行已经算过的左边信息 这就说明二维数组可以压成一维。 一维数组的含义 令 \( dp[j] \) 表示“当前处理到某一行时，该行第 \(j\) 列的最小路径和”。 那么更新时： 更新前的 dp[j] 表示上一行的值 更新后的 dp[j-1] 表示当前行左侧的值 于是 \( dp[j] = \min(dp[j],\ dp[j-1]) + a[i][j] \) 这正是滚动数组最值得体会的地方：同一个数组元素，在不同时间点含义不同。 int main() { vector<vector<int>> a = { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }; int n = a.size(), m = a[0].size(); vector<int> dp(m, 0); dp[0] = a[0][0]; for (int j = 1; j < m; j++) dp[j] = dp[j - 1] + a[0][j]; for (int i = 1; i < n; i++) { dp[0] += a[i][0]; for (int j = 1; j < m; j++) { dp[j] = min(dp[j], dp[j - 1]) + a[i][j]; } } cout << dp[m - 1] << "\n"; } 复杂度 空间复杂度已经降到 \( O(m) \) 很多动态规划问题，如果某些数据再也用不到了，都有可能有空间优化的可能。 第二题：加入障碍物或改变移动方式 有些格子是障碍，不能经过。其余格子有代价。仍然只能向右或向下，求从左上到右下的最小路径和。 如果 \((i,j)\) 是障碍，那么这个状态直接无效。可以把它看作正无穷。否则，若它不是障碍，才有正常转移： \[dp[i][j] = \begin{cases} +\infty, & \text{若 } (i,j) \text{ 是障碍} \\ \min(dp[i-1][j],\ dp[i][j-1]) + a[i][j], & \text{否则} \end{cases} \] 和上一题相比，变化不大，但非常典型。它提醒我们：动态规划不是先背一个式子，而是先想“当前状态是否存在”，再想“它从哪里来”。 另一个经典升级方式，是不再只允许“右”和“下”两种动作。比如，允许向右下对角线行走。此时到达 \((i,j)\) 的最后一步可能来自三个位置： \((i-1,j)\) \((i,j-1)\) \((i-1,j-1)\) 所以 \( dp[i][j] = \min\{dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]\} + a[i][j] \) 当条件改变时，遇到新题时，一定要理清当前状态是什么？它能从哪些状态过来？ 情况一下我们仍可应用滚动数组，而情况二下，除了“上方”和“左方”，还必须再额外保存“左上方”的旧值。最终仍只需要一维空间。 第三题：恰好经过 \(k\) 个特殊格子 现在我们还是要走格子，不过不是要最小化代价，而是要求出总方案数量。某些格子是“特殊格子”，要求从左上走到右下，路径上恰好经过 \(k\) 个特殊格子。这时如果你只记录当前坐标，就无法区分： 走到同一个位置，但已经经过了 1 个特殊格子 走到同一个位置，但已经经过了 3 个特殊格子 这两种情况显然不能混在一起。设 \( dp[i][j][t] \) 表示走到 \((i,j)\) 时，恰好经过了 \(t\) 个特殊格子的方案数。 设 \(special(i,j)\) 表示当前格子是否特殊，取值为 \(0\) 或 \(1\)。那么从上方或左方转移过来时，特殊格子的数量要跟着变化：\( dp[i][j][t] = dp[i-1][j][t-special(i,j)] + dp[i][j-1][t-special(i,j)] \) 当然，这个式子只在下标合法时成立。为了简化边界判断，有不合法下标的项就直接取 0. int main() { int n = 3, m = 3, K = 2; vector<vector<int>> sp = { {0, 1, 0}, {1, 0, 1}, {0, 0, 1} }; vector<vector<vector<long long>>> dp( n, vector<vector<long long>>(m, vector<long long>(K + 1, 0)) ); if (sp[0][0] <= K) dp[0][0][sp[0][0]] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (i == 0 && j == 0) continue; int add = sp[i][j]; for (int t = add; t <= K; t++) { if (i > 0) dp[i][j][t] += dp[i - 1][j][t - add]; if (j > 0) dp[i][j][t] += dp[i][j - 1][t - add]; } } } cout << dp[n - 1][m - 1][K] << "\n"; } 第四题：双人走格子 两个人同时从左上角走到右下角，每次都只能向右或向下。每个格子有收益，但如果两个人经过同一个格子，这个格子的收益只能算一次，问总收益最大是多少。 这个模型也可以理解成：一个人从起点走到终点，再从终点走回来，经过的格子不能重复计分。 最直接的想法是：\( dp[x_1][y_1][x_2][y_2] \) 表示两个人分别走到 \((x_1,y_1)\) 和 \((x_2,y_2)\) 的最优收益。这样的维度太高了，既难写，也不优雅。 压缩空间 如果两个人都从起点出发，每次都只走一步，那么当他们“同时”走到某个阶段时，步数一定相同。 设当前总步数为 \(k\)，那么： 第一个人在 \((i_1,\ k-i_1)\) 第二个人在 \((i_2,\ k-i_2)\) 于是四维状态就可以压成三维： \[dp[k][i_1][i_2] \] 表示两个人都走了 \(k\) 步时，分别位于上述两个位置时的最大收益。 转移 因为每个人每一步只有“向下”或“向右”两种选择，所以两个人合起来一共有四种转移来源： 两人都从上面来 第一个从上面来，第二个从左边来 第一个从左边来，第二个从上面来 两人都从左边来 所以当前状态的来源是四个候选状态中的最大值，再加上当前位置的收益。设两人当前位置分别是 \((x_1,y_1)\) 和 \((x_2,y_2)\)，则本轮新增收益为： \[\text{gain} = \begin{cases} a[x_1][y_1], & (x_1,y_1) = (x_2,y_2) \\ a[x_1][y_1] + a[x_2][y_2], & \text{否则} \end{cases} \] int main() { int n = 3; vector<vector<int>> a = { {1, 2, 3}, {0, 4, 5}, {2, 1, 6} }; const int NEG = -1e9; vector<vector<vector<int>>> dp( 2 * n - 1, vector<vector<int>>(n, vector<int>(n, NEG)) ); dp[0][0][0] = a[0][0]; for (int k = 1; k <= 2 * n - 2; k++) { for (int i1 = 0; i1 < n; i1++) { for (int i2 = 0; i2 < n; i2++) { int j1 = k - i1; int j2 = k - i2; if (j1 < 0 || j1 >= n || j2 < 0 || j2 >= n) continue; int best = NEG; for (int di1 = 0; di1 <= 1; di1++) { for (int di2 = 0; di2 <= 1; di2++) { int pi1 = i1 - di1; int pi2 = i2 - di2; int pj1 = (k - 1) - pi1; int pj2 = (k - 1) - pi2; if (pi1 < 0 || pi2 < 0 || pj1 < 0 || pj2 < 0) continue; best = max(best, dp[k - 1][pi1][pi2]); } } if (best == NEG) continue; int gain = a[i1][j1]; if (i1 != i2 || j1 != j2) gain += a[i2][j2]; dp[k][i1][i2] = best + gain; } } } cout << dp[2 * n - 2][n - 1][n - 1] << "\n"; } 总结 “走格子”看起来像一类很小的题型，但它其实浓缩了动态规划里最核心的东西： 状态设计 前驱分析 边界初始化 遍历顺序 空间优化 维度扩展 我们需要设计：状态是什么？需要几个维度来表示？当前状态从哪里来？边界和初始条件从哪里来？遍历的顺序是什么？