最小路径和如何用动态规划求解？为什么只能从上方或左方转移？

简化版

最小路径和用 dp[i][j] 表示从左上角走到 (i,j) 的最小代价。因为每步只能向右或向下，所以到达当前格子只可能来自上方或左方，转移就是 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。

详细版

这类题的关键是把“从起点到终点的整条路径”拆成“到每个格子的最优代价”。如果题目限制只能向右、向下走，那么路径天然没有环，并且 (i,j) 的上一步只可能是 (i-1,j) 或 (i,j-1)。因此先计算第一行和第一列，再按行列顺序填表即可。

边界处理有两种常见写法：一种是单独初始化第一行、第一列；另一种是使用无穷大哨兵数组。时间复杂度是 O(mn)，空间复杂度可以从 O(mn) 优化到 O(n)，因为每次只依赖上一行当前位置和当前行左侧位置。

完整版教学

一、先把路径问题变成“到达某点的最优代价”

最小路径和看起来是在问一整条路线，但动态规划更喜欢问局部问题：走到每个格子时，已经付出的最小代价是多少。这样一来，终点答案不是凭空计算出来的，而是由它的前驱格子一步一步推过来的。

如果矩阵是 3 x 3，起点在 (0,0)，终点在 (2,2)，我们真正维护的是 9 个状态，而不是枚举所有路径。路径越长，枚举数量增长越快；状态表只和格子数量成正比。

(0,0) -> ... -> (2,2)
  ↓
每个格子都记录：到这里的最小路径和

这种视角的好处是，只要当前格子的最优值确定，后面的格子就可以放心使用它。

二、为什么当前格只看上方和左方

题目通常限制“只能向右或向下”。反过来看，如果你现在站在 (i,j)，上一格只能是 (i-1,j) 或 (i,j-1)。这就是转移范围的来源，不是模板硬背。

当前限制	到达 `(i,j)` 的可能前驱
只能向右、向下	上方、左方
可以四向移动	可能出现环，普通 DP 不够
只能向右、向下、右下	上方、左方、左上方

记忆钩子：看到矩阵 DP，先问“我从哪里来”，而不是先背公式。

如果允许向上或向左，状态之间可能互相依赖，简单按行填表就会失效，可能要改成图最短路。

三、状态定义和转移公式怎么来

定义：

dp[i][j] = 从 grid[0][0] 走到 grid[i][j] 的最小路径和

到 (i,j) 的最后一步有两种来源：

来自上方：dp[i-1][j] + grid[i][j]
来自左方：dp[i][j-1] + grid[i][j]

取更小的那条路：

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

这里的 grid[i][j] 只加一次，因为无论从上方还是左方进入当前格，最终都要踩到当前格。

四、用具体数字走一遍表

假设矩阵如下：

1 3 1
1 5 1
4 2 1

第一行只能一路向右：1, 4, 5。第一列只能一路向下：1, 2, 6。中间格 (1,1) 的值是 min(4,2)+5=7，右下角最终会得到 7。

这张表也解释了为什么不是局部贪心。比如从起点看到右边是 3、下边是 1，局部选小不代表后面一定最优；DP 保存的是到达每个位置的全局最优前缀。

五、代码实现与边界初始化

常见 Java 写法如下：

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 i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][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++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[m - 1][n - 1];
}

第一行没有上方，第一列没有左方，所以要单独初始化。也可以用 m+1、n+1 的数组配合大数哨兵，但要小心起点不要被哨兵污染。

六、空间优化为什么可以做

第 i 行的 dp[j] 在更新前表示上一行的 dp[i-1][j]，dp[j-1] 表示当前行左边的 dp[i][j-1]。所以二维表可以压成一维。

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

空间优化不是必须，但面试追问时能说明依赖关系，会比只写二维数组更稳。

七、常见误区与追问

误区：每一步都走当前较小的相邻格。 局部最小不保证后续代价小，动态规划比较的是完整前缀路径。
误区：忘记初始化第一行和第一列。 边界格只有一种来源，不能套用普通转移。
误区：把当前格代价加了两次。 公式里只在选完前驱后加一次 grid[i][j]。
追问：如果允许向上和向左还能这样做吗？ 不一定，可能出现环，通常要考虑最短路算法。
追问：空间为什么能优化到一维？ 因为每个状态只依赖上一行同列和当前行左列。
追问：如果要输出路径怎么办？ 需要记录每个格子的前驱方向，最后从终点回溯。

八、加强记忆

最小路径和的核心链条是：限制方向决定前驱，前驱决定转移，边界决定初始化。记住“到当前格的最小代价”这个状态，看到只能右下走，就立刻想到上方和左方二选一。二维表负责讲清楚逻辑，一维数组负责优化空间；面试先写稳二维，再解释如何压缩，通常最安全。

简化版

详细版