最小路径和 图解题解

最小路径和这道题在问什么

一个 m×n 的网格，每格有一个非负数字。从左上角 (0,0) 出发，每步只能向右或向下走一格，到达右下角 (m-1,n-1)，求沿途数字之和最小是多少。两个隐含条件值得先记下：只能右、下两个方向，意味着路径不会走回头路；格子里的数非负，意味着不存在「绕远反而更省」的怪路。

为什么不能枚举所有路径

暴力思路是回溯出每一条从左上到右下的路径、逐条算和取最小。但路径条数是组合级的：每条路要走 m-1 步向下、n-1 步向右，排列方式随网格增大爆炸式增长，稍大的网格就算不完。

浪费在哪里？海量路径共享着相同的前半段。其实走到任何一个格子 (i,j) 时，前面那段路怎么绕的根本不重要，对后续决策有用的信息只有一个数：到这里的最小花费。把每个格子的这个数记下来复用，指数条路径就坍缩成 m×n 个子问题——这就是无后效性的白话版：到达 (i,j) 之后怎么走，与之前的路线无关。

dp 转移方程为什么是 min 加本格

定义 dp[i][j] 为从起点走到 (i,j) 的最小路径和。任何到达 (i,j) 的路，最后一步只有两种可能：从上方 (i-1,j) 下来，或从左方 (i,j-1) 过来。走上方来路的最优花费是 dp[i-1][j]，走左方来路的最优是 dp[i][j-1]，二者取小、再加上本格数字，就是 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。

为什么这样就是对的？假如最优路径经由上方进入 (i,j)，它在 (i-1,j) 之前的部分必然也是到 (i-1,j) 的最优——否则把那段换成更省的，总和还能更小，与最优矛盾。所以只需比较两条来路各自的最优值。注意是取 min 不是相加：一条路只能从一个方向进来，把两个来路加在一起没有物理意义，这是初学者最常写错的一笔。

首行和首列为什么要单独处理

第一行的格子上方没有邻居，只能从左边一路走过来，所以是前缀累加：dp[0][j] = dp[0][j-1] + grid[0][j]；第一列同理只能从上面来。如果不单独处理、对不存在的方向也去取 min，要么数组越界，要么取到未初始化的 0 而把答案算小。起点 dp[0][0] 就是 grid[0][0] 本身。打好这一行一列的底，内部格子逐行推过去，右下角 dp[m-1][n-1] 即答案——对示例那个 4×5 网格，结果是 22。

复杂度多少，空间还能怎么省

每个格子恰好算一次、每次 O(1)，时间 O(m×n)；存整张表空间 O(m×n)。因为 dp[i][j] 只依赖上一行同列和本行左邻，可以用一维数组滚动：dp[j] = grid[i][j] + min(dp[j], dp[j-1])，其中 dp[j] 更新前恰好是上一行的值、dp[j-1] 是本行刚算完的左邻，空间降到 O(n)。若题目允许改输入，甚至能直接在 grid 上原地累加做到 O(1) 额外空间。最后提醒：答案在右下角那格，别返回错位置。

Python

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0]*n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    return dp[m-1][n-1]

C++

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

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 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];