LeetCode_动态规划_中等_64.最小路径和

素颜马尾好姑娘i 2023-10-06 19:01 17阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。  
说明：每次只能向下或者向右移动一步。

**示例 1：**  
![在这里插入图片描述][b13830bcd86a49eb838e27c49c47e833.png]  
输入：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\] <= 100

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/minimum-path-sum

## 2.思路 ##

（1）动态规划  
由题可定义 (m + 1) \* (n + 1) 的二维数组 dp，并且dp\[i\]\[j\] 表示从起点 (1, 1) 到终点 (i, j) 的最小路径和 (1 ≤ i ≤ m, 1 ≤ j ≤ n)。分析可知：

*  对于网格中第一行的位置（即 i = 1），从起点 (1, 1) 到终点 (i, j) 的最小路径和就等于 `dp[i][j - 1] + grid[i - 1][j - 1]`；
 *  对于网格中第一列的位置（即 j = 1），从起点 (1, 1) 到终点 (i, j) 的最小路径和就等于 `dp[i - 1][j] + grid[i - 1][j - 1]`；
 *  对于其余位置，从起点 (1, 1) 到终点 (i, j) 的最小路径和 dp\[i\]\[j\]，就等于grid\[i - 1\]\[j - 1\]加上**与终点 (i, j) 相邻的位置的最小路径和中的最小值**，最后再根据以上情况编写代码即可。

相关题目：  
[LeetCode\_动态规划\_中等\_120.三角形最小路径和][LeetCode_120.]

## 3.代码实现（Java） ##

//思路1————动态规划
    class Solution {
        
        public int minPathSum(int[][] grid) {
        
            int m = grid.length;
            int n = grid[0].length;
            //dp[i][j] 表示从起点 (1, 1) 到终点 (i, j) 的最小路径和 (1 ≤ i ≤ m, 1 ≤ j ≤ n)
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
        
                for (int j = 1; j <= n; j++) {
        
                    if (i == 1) {
        
                        //网格中第一行的位置
                        dp[i][j] = grid[i - 1][j - 1] + dp[i][j - 1];
                    } else if (j == 1) {
        
                        //网格中第一列的位置
                        dp[i][j] = grid[i - 1][j - 1] + dp[i - 1][j];
                    } else {
        
                        //其余位置
                        dp[i][j] = grid[i - 1][j - 1] + Math.min(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            return dp[m][n];
        }
    }
    
    //实际上可以直接在 grid 中进行修改，不需要使用额外的空间
    class Solution {
        
        public int minPathSum(int[][] grid) {
        
            int m = grid.length;
            int n = grid[0].length;
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (i == 0 && j == 0) {
        
                        continue;
                    }
                    if (i == 0) {
        
                        grid[i][j] = grid[i][j - 1] + grid[i][j];
                    } else if (j == 0) {
        
                        grid[i][j] = grid[i - 1][j] + grid[i][j];
                    } else {
        
                        grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
                    }   
                }
            }
            return grid[m - 1][n - 1];
        }
    }

[b13830bcd86a49eb838e27c49c47e833.png]: https://img-blog.csdnimg.cn/b13830bcd86a49eb838e27c49c47e833.png
[LeetCode_120.]: https://blog.csdn.net/weixin_43004044/article/details/125944499