Medium

题目描述

给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明： 每次只能向下或者向右移动一步。

示例 1：

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

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200

解题思路

这是一道经典的动态规划问题。我们需要找到从左上角到右下角的最小路径和，且只能向右或向下移动。

思路分析：

我们可以用动态规划来解决这个问题。设 dp[i][j] 表示从起点 (0,0) 到位置 (i,j) 的最小路径和。

状态转移方程为：

  • 对于第一行：dp[0][j] = dp[0][j-1] + grid[0][j]（只能从左边来）
  • 对于第一列：dp[i][0] = dp[i-1][0] + grid[i][0]（只能从上面来）
  • 对于其他位置：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

优化方案：

  1. 空间优化：可以直接在原数组上修改，将空间复杂度从 O(mn) 降到 O(1)
  2. 一维数组优化：使用一维数组滚动更新，空间复杂度 O(n)

这里我们采用原地修改的方法，既简洁又高效。

代码实现

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 初始化第一行
        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] += min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        
        return grid[m - 1][n - 1];
    }
};

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 初始化第一行
        for j in range(1, n):
            grid[0][j] += grid[0][j - 1]
        
        # 初始化第一列
        for i in range(1, m):
            grid[i][0] += grid[i - 1][0]
        
        # 填充其余位置
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
        
        return grid[m - 1][n - 1]

public class Solution {
    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];
    }
}

var minPathSum = function(grid) {
    const m = grid.length, n = grid[0].length;
    
    // 初始化第一行
    for (let j = 1; j < n; j++) {
        grid[0][j] += grid[0][j - 1];
    }
    
    // 初始化第一列
    for (let i = 1; i < m; i++) {
        grid[i][0] += grid[i - 1][0];
    }
    
    // 填充其余位置
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
        }
    }
    
    return grid[m - 1][n - 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(mn)需要遍历整个网格一次
空间复杂度O(1)原地修改，不使用额外空间

相关题目