⭐ 题目日期：

字节 - 2024/11/1

🌳 题目描述：

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

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

示例 1：

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

🕵🏽 面试评估：

这道题考查动态规划，难度中等偏上

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

设 DP[i][j] 表示从位置 (i, j) 到右下角的最短距离。从 (i, j) 可以向右 (i, j + 1) 走一步或者向下 (i + 1, j) 走一步。因此我们可以得出状态转移方程：

DP[i] [j] = grid[i] [j] + Min(DP[i] [j + 1], DP[i + 1] [j]);

基准：DP[m - 1] [n - 1] = grid[m - 1] [n - 1]; 因为右下角到右下角的路径是它自己。

接下来就是填充数据，从右下角出发，自下而上，一列一列填充。

💻代码(Java、Python、C++)：

Java

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int down = i >= m - 1 ? Integer.MAX_VALUE : grid[i + 1][j];
                int right = j >= n - 1 ? Integer.MAX_VALUE : grid[i][j + 1];
                grid[i][j] += down == Integer.MAX_VALUE && right == Integer.MAX_VALUE ? 0 : Math.min(down, right);
            }
        }

        return grid[0][0];
    }

Python

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                down = grid[i + 1][j] if i < m - 1 else float('inf')
                right = grid[i][j + 1] if j < n - 1 else float('inf')
                if down != float('inf') or right != float('inf'):
                    grid[i][j] += min(down, right)

        return grid[0][0]

C++

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int down = i >= m - 1 ? INT_MAX : grid[i + 1][j];
                int right = j >= n - 1 ? INT_MAX : grid[i][j + 1];
                grid[i][j] += down == INT_MAX && right == INT_MAX ? 0 : min(down, right);
            }
        }

        return grid[0][0];
    }
};

🚵🏻复杂度分析：

矩阵 m 行，n 列

时间复杂度: O(mn), 矩阵所有的元素遍历一遍

空间复杂度: O(1), 原地存储路径的累加和。如果不允许修改原数组，需要额外的空间存储，空间复杂度可优化至 O(m)

🔬在线评测(Online Judge):

题目链接