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

很多人第一次接触动态规划，都是从“走格子”开始的：在一个二维网格上，从起点走到终点，每次只能做有限几种移动，问方案数、最小代价，或者最大收益。 第一题：最小路径和 给定一个 \(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] \) 这正是滚动数组最值得体会的地方：同一个数组元素，在不同时间点含义不同。