06 矩阵路径DP：网格出发的二维状态转移

矩阵路径 DP：网格出发的二维状态转移

摘要

矩阵路径 DP 是动态规划中入门门槛最低、但变体最丰富的一类题型。从最简单的”不带障碍的路径计数”，到”带障碍物的唯一路径”，再到”最小代价路径”和”地下城游戏”，每一道题都是对二维 DP 状态设计和初始化技巧的一次深化。本文系统梳理四道经典网格 DP 题，重点讲解障碍物初始化陷阱、反向 DP（从终点到起点）和空间优化技巧，帮助你建立应对所有二维路径问题的通用思维框架。

---

第 1 章 二维路径 DP 的基础结构

1.1 网格 DP 的通用特征

网格（矩阵）DP 的输入通常是一个 $m\times n$ 的二维数组。每道题的目标不同，但共享以下几个特征：

1. 状态是位置：dp[i][j] 表示”到达（或从）位置 (i, j) 的某种最优值”
2. 转移来自相邻格子：通常是”从上方来”或”从左方来”（向右向下走）
3. 边界需要特别初始化：第一行和第一列只有一个来源方向
4. 答案在角落：通常是 dp[m-1][n-1] 或 dp[0][0]

1.2 移动方向约束的重要性

大多数网格 DP 题只允许向右或向下移动（不能回头）。这个约束至关重要，因为它保证了”当前格的值只依赖已经计算过的格”——即转移方向和遍历方向一致，不会出现循环依赖。

如果允许四方向移动（上下左右），则不能直接用简单的二维 DP，需要 BFS/DFS 或其他方法。

---

第 2 章 LeetCode 62：不同路径 I

2.1 题目

LeetCode 62 - Unique Paths（中等）

一个机器人位于一个 $m\times n$ 网格的左上角（(0, 0)）。机器人每次只能向下或者向右移动一步。机器人试图到达网格的右下角（(m-1, n-1)）。问共有多少条不同的路径？

输入: m = 3, n = 7
输出: 28

输入: m = 3, n = 2
输出: 3
解释: 从左上角到右下角，共有 3 条路径：
     1. 右 → 下 → 下
     2. 下 → 右 → 下
     3. 下 → 下 → 右

2.2 四步法推导

第一步：识别。求路径总数 → 计数问题。子问题重叠（到达 (i,j) 的路径数由到达 (i-1,j) 和 (i,j-1) 的路径数决定）。✅

第二步：定义状态。dp[i][j] = 从左上角 (0,0) 到 (i,j) 的不同路径数。

第三步：转移方程。到达 (i, j) 只能从上方 (i-1, j) 或左方 (i, j-1) 来：

$dp[i][j]=dp[i-1][j]+dp[i][j-1]$

第四步：初始化。

• 第一行 dp[0][j] = 1（只能一路向右，只有 1 条路径）
• 第一列 dp[i][0] = 1（只能一路向下，只有 1 条路径）

2.3 实现

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
 
    // 第一行和第一列初始化为 1
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
 
    // 从 (1,1) 开始填表
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

空间优化：dp[i][j] 只依赖上一行和左方，可以用一维数组：

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);  // 初始化为第一行（全 1）
 
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];  // dp[j]（上一行同列）+= dp[j-1]（同行左方）
        }
    }
    return dp[n - 1];
}

2.4 数学公式：组合数

路径数实际上可以直接用组合数计算：从起点到终点需要走 (m-1) 步向下和 (n-1) 步向右，共 (m+n-2) 步，从中选 (m-1) 步向下：

$C(m+n-2,m-1)=\frac{(m+n-2)!}{(m-1)!(n-1)!}$

但 DP 解法在面试中更通用（面对障碍物变体时，组合数公式失效，DP 仍然适用）。

---

第 3 章 LeetCode 63：不同路径 II（带障碍物）

3.1 题目

LeetCode 63 - Unique Paths II（中等）

在 $m\times n$ 的网格中，某些格子被标为障碍物（值为 1），不能经过。求从左上角到右下角的不同路径数。

输入: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出: 2
解释: 中间有一个障碍物，可以绕上或绕下，共 2 条路径。

输入: obstacleGrid = [[0,1],[0,0]]
输出: 1

3.2 障碍物的处理

加上障碍物后，状态转移的逻辑基本不变，只需要额外处理：

1. 障碍物格子的 dp 值为 0（无法到达）
2. 初始化时的陷阱：第一行或第一列中，一旦遇到障碍物，其后（右方/下方）的所有格子都无法到达

障碍物初始化的关键陷阱：

// 错误做法：直接对所有第一行/列设 dp=1，然后对障碍物设 dp=0
for (int j = 0; j < n; j++) dp[0][j] = 1;        // ❌ 错误
for (int i = 0; i < m; i++) dp[i][0] = 1;        // ❌ 错误
// 然后对障碍物设 0……但障碍物后面的格子仍然是 1！
 
// 正确做法：遇到障碍物就 break，其后全部为 0
for (int j = 0; j < n; j++) {
    if (grid[0][j] == 1) break;  // 一旦遇到障碍物，后续全部无法到达
    dp[0][j] = 1;
}
for (int i = 0; i < m; i++) {
    if (grid[i][0] == 1) break;
    dp[i][0] = 1;
}

考虑这个情况：grid = [[0, 0, 1, 0, 0]]（只有一行）。如果不处理 break，第 4 和第 5 列会被设为 1，实际上根本无法到达（障碍物在第 3 列堵死了所有路径）。

3.3 完整实现

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
 
    // 起点或终点有障碍物，直接返回 0
    if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;
 
    int[][] dp = new int[m][n];
    dp[0][0] = 1;
 
    // 初始化第一列：遇到障碍物后，下面全是 0（break 后 dp 保持默认 0）
    for (int i = 1; i < m; i++) {
        if (obstacleGrid[i][0] == 1) break;
        dp[i][0] = dp[i - 1][0];  // 没有障碍物，继承上方
    }
    // 初始化第一行
    for (int j = 1; j < n; j++) {
        if (obstacleGrid[0][j] == 1) break;
        dp[0][j] = dp[0][j - 1];  // 没有障碍物，继承左方
    }
 
    // 填表
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0;  // 障碍物，无法到达
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    return dp[m - 1][n - 1];
}

生产避坑：障碍物初始化必须用 break

如果第一行/列中某个格子是障碍物，其后（右方/下方）的所有格子都无法从起点经单方向到达。因此初始化时遇到障碍物必须立即 break，不能继续往后设 1。这是网格 DP 中最常见的 off-by-one 错误。

---

第 4 章 LeetCode 64：最小路径和

4.1 题目

LeetCode 64 - Minimum Path Sum（中等）

给定一个包含非负整数的 $m\times n$ 网格 grid，从左上角到右下角，只能向右或向下移动，求路径上数字总和最小的路径。

输入: grid = [[1,3,1],[1,5,1],[4,2,1]]
输出: 7
解释: 路径 1→3→1→1→1 的总和最小。

4.2 推导

状态：dp[i][j] = 从起点 (0,0) 到 (i,j) 的最小路径和。

转移：

$dp[i][j]=grid[i][j]+\min (dp[i-1][j],dp[i][j-1])$

初始化：

• dp[0][0] = grid[0][0]
• 第一行：dp[0][j] = dp[0][j-1] + grid[0][j]（只能一路向右，累加）
• 第一列：dp[i][0] = dp[i-1][0] + grid[i][0]（只能一路向下，累加）

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
 
    dp[0][0] = grid[0][0];
 
    // 初始化第一行和第一列
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
    for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
 
    // 填表
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m - 1][n - 1];
}

4.3 原地修改：空间 O(1) 的技巧

如果允许修改输入数组，可以把 dp 直接写回 grid，空间 $O(1)$：

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
 
    for (int j = 1; j < n; j++) grid[0][j] += grid[0][j - 1];
    for (int i = 1; i < m; i++) grid[i][0] += grid[i - 1][0];
 
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
        }
    }
    return grid[m - 1][n - 1];
}

生产避坑：原地修改的副作用

原地修改输入会改变调用方传入的数组，在工程中通常是不好的实践（side effect）。面试中如果使用原地修改，应主动说明”如果不能修改输入，我会使用额外的 dp 数组”。

---

第 5 章 LeetCode 120：三角形最小路径和

5.1 题目

LeetCode 120 - Triangle（中等）

给定一个三角形 triangle，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。

输入: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出: 11
解释: 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

5.2 正向 DP vs 反向 DP

正向 DP（从顶到底）：

dp[i][j] = 从顶 (0,0) 到 (i,j) 的最小路径和。

转移：dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])

但 j = 0 时只能从 dp[i-1][0] 来（没有左上方），j = i 时只能从 dp[i-1][i-1] 来（没有正上方）。需要特别处理边界。

最终答案：min(dp[n-1][0], dp[n-1][1], ..., dp[n-1][n-1])（底部所有位置取最小）。

反向 DP（从底到顶）——更优雅的解法：

dp[i][j] = 从 (i,j) 出发到底部的最小路径和。

转移：dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])（向左下或右下走）

初始化：dp[n-1][j] = triangle[n-1][j]（底部，已到终点）

最终答案：dp[0][0]（从顶部出发的最小路径和，只有一个值）

反向 DP 的优势：

1. 边界条件更简单（底部初始化无需特判）
2. 最终只需返回一个值 dp[0][0]，不用再对最后一行取最小
3. 可以直接原地修改（从底部往上更新）

public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    // 用底部一行初始化 dp
    int[] dp = new int[n];
    for (int j = 0; j < n; j++) {
        dp[j] = triangle.get(n - 1).get(j);
    }
 
    // 从倒数第二行往上推
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {  // 第 i 行有 i+1 个元素
            dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
            // dp[j]   = dp[i+1][j]（右下方）
            // dp[j+1] = dp[i+1][j+1]（左下方，实际上是 j+1 位置）
        }
    }
    return dp[0];
}

核心概念：反向 DP 的适用场景

当”正向 DP 的最终答案需要取一段范围的最优值”时，考虑反向 DP（从终点出发，推到起点）。反向 DP 把”在哪里终止”的不确定性消除——终止点已知（底部所有格），不确定的是起点。 三角形、地下城游戏（见下一节）都适合反向 DP。

---

第 6 章 LeetCode 174：地下城游戏

6.1 题目

LeetCode 174 - Dungeon Game（困难）

恶魔抓住了公主并将她关在了地下城 dungeon 的右下角。骑士从左上角出发，每次只能向右或向下移动，要到达公主所在位置。

地下城中的房间可能包含魔法球（正数，增加血量）或恶魔（负数，减少血量）。骑士的血量在任何时候都不能降至 0 以下。

给定地下城，求骑士出发时的最小初始血量。

输入: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出: 7
解释: 初始血量至少为 7。路径：右 → 右 → 下。
     血量变化：7 → 5 → 8 → 11 → 12 → 7

6.2 为什么正向 DP 失败

尝试正向 DP：dp[i][j] = 到达 (i,j) 时的最大剩余血量。

问题：最大剩余血量不等于最少初始血量。路径 A 到达终点时血量 100，但中途血量可能降到 0（死亡）；路径 B 到达终点时血量 1，但中途血量从未降到 0。最大剩余血量这个指标，没有捕捉到”中途不能死亡”这个约束。

换个状态：dp[i][j] = 从 (i,j) 出发，到达终点所需的最低血量。这样，“到 (i,j) 之前需要多少血量”就可以通过 dungeon[i][j] + dp[i][j] 来计算——如果 dungeon[i][j] 是负数（陷阱），需要的血量更多；如果是正数（治疗），需要的血量可以少一些。

6.3 反向 DP 推导

状态：dp[i][j] = 从 (i,j) 出发到达终点所需的最低血量（进入 (i,j) 时的最低血量）。

初始化：

dp[m-1][n-1]：在终点的状态。进入终点后，血量 = 1 + dungeon[m-1][n-1]（如果终点是负值，需要血量抵消；如果是正值，只需至少 1 点血量）：

$dp[m-1][n-1]=\max (1,1-dungeon[m-1][n-1])$

转移方程：

从 (i,j) 可以往右 (i,j+1) 或往下 (i+1,j)。进入 (i,j) 时需要的最低血量，等于：

从 (i,j) 离开后需要的血量（min(dp[i][j+1], dp[i+1][j])）减去 dungeon[i][j]（因为 dungeon[i][j] 会改变血量），且至少为 1：

$dp[i][j]=\max (1,\min (dp[i][j+1],dp[i+1][j])-dungeon[i][j])$

边界：最后一行只能向右，最后一列只能向下，单独处理。

public int calculateMinimumHP(int[][] dungeon) {
    int m = dungeon.length, n = dungeon[0].length;
    int[][] dp = new int[m + 1][n + 1];
 
    // 初始化：在范围外的格子设为 Integer.MAX_VALUE，防止越界时被选中
    for (int i = 0; i <= m; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
    dp[m][n - 1] = 1;  // 等价于 dp[m-1][n] 和 dp[m][n-1]，用哨兵代替边界
    dp[m - 1][n] = 1;
 
    // 从右下角往左上角填表
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int minNext = Math.min(dp[i + 1][j], dp[i][j + 1]);  // 下一步的最低需求
            dp[i][j] = Math.max(1, minNext - dungeon[i][j]);       // 进入此格的最低血量
        }
    }
    return dp[0][0];
}

时间复杂度：$O(mn)$。空间复杂度：$O(mn)$，可用一维数组优化。

6.4 哨兵技巧解析

在 dp[m][n-1] = 1 和 dp[m-1][n] = 1 设置了两个哨兵，这样对终点 (m-1, n-1) 的转移也能套用通用公式：

dp[m-1][n-1] = max(1, min(dp[m-1][n], dp[m][n-1]) - dungeon[m-1][n-1]) = max(1, 1 - dungeon[m-1][n-1])

这正是终点的正确初始值。哨兵技巧消除了特判终点的代码，让逻辑更统一。

---

第 7 章 二维路径 DP 的变体模式

7.1 方格骑士（多次经过同一格）

LeetCode 741 - Cherry Pickup（困难）

两次从起点到终点取樱桃（路径不同），求最多能取多少樱桃。

难点：不能用”去程 DP + 回程 DP”的贪心——两次独立 DP 不能保证两条路径的总和最优。

正确建模：同时模拟两个人从起点出发，用三维 DP：dp[t][r1][r2]，其中 t 是步数，r1 和 r2 是两个人的行坐标（列坐标由 c = t - r 推出）。

7.2 最长递增路径（四方向移动）

LeetCode 329 - Longest Increasing Path in a Matrix

矩阵中，每次可以向上下左右四方向移动，只能移动到更大的数字。求最长路径长度。

由于可以四方向移动，无法直接按行/列顺序做 DP（循环依赖）。解法：DFS + 记忆化搜索（memo[i][j] = 从 (i,j) 出发的最长路径）。这是 DFS 类的记忆化 DP，本质上是拓扑序上的 DP（DAG 保证了无环，因为只能走到更大的数字）。

7.3 路径 DP 与背包的结合

LeetCode 688 - Knight Probability in Chessboard

骑士走 k 步，求留在棋盘上的概率。

dp[k][i][j] = 第 k 步时在 (i,j) 的概率。转移：遍历所有 8 个方向，如果 (i',j') 在棋盘内则转移。

这是路径 DP 和概率计算的结合，说明网格 DP 的状态不局限于”最小值/最大值/计数”。

---

第 8 章 网格 DP 的初始化总结与对比

8.1 各题初始化方式汇总

题目	起点	终点	初始化策略
不同路径 I	(0,0)	(m-1,n-1)	第一行/列全为 1
不同路径 II	(0,0)	(m-1,n-1)	第一行/列遇障碍 break
最小路径和	(0,0)	(m-1,n-1)	第一行/列累加
三角形	顶部 (0,0)	底部任意	反向 DP，底部初始化
地下城游戏	(0,0)	(m-1,n-1)	反向 DP，终点设哨兵

8.2 选择正向还是反向 DP 的依据

选正向 DP 的情况：

• 起点固定，终点固定
• 状态值由”如何到达该点”决定（如最小路径和：到达 (i,j) 需要多少代价）

选反向 DP 的情况：

• 终点固定，但”出发条件”（起点的初始状态）不确定
• 状态值由”从该点出发到终点”决定（如地下城：从 (i,j) 出发至少需要多少血量）
• 正向 DP 的最终答案需要对一段区间取 min/max（如三角形底部取最小值），不如用反向 DP 让答案集中在一个位置

---

小结

本文通过五道经典网格 DP 题，系统梳理了二维路径 DP 的核心技术：

1. Unique Paths I：基础路径计数，dp[i][j] = dp[i-1][j] + dp[i][j-1]
2. Unique Paths II：障碍物处理，初始化时遇障碍 break，避免”穿越”障碍物
3. Minimum Path Sum：最小代价路径，dp[i][j] = grid[i][j] + min(上, 左)
4. Triangle：三角形最小路径，反向 DP 消除边界特判，答案汇聚在 dp[0][0]
5. Dungeon Game：地下城游戏，反向 DP + 哨兵处理终点，约束”血量不能为负”

下一篇区间DP：戳气球、矩阵链乘与「从小区间到大区间」将介绍 DP 中最需要”反直觉”思维的类型——区间 DP，重点讲解为什么枚举区间长度比枚举起点更安全。