最小路径和

快来打我* 2022-12-05 10:25 137阅读 0赞

# 最小路径和 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/minimum-path-sum/

## 2、题目要求 ##

> 题目描述

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

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

> **示例:**

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

## 3、代码思路 ##

> 方法一：深度优先搜索

1.  这感觉就和迷宫问题一样，按照先下后右(或者先右后下)的方式进行递归，当小人走到矩形外面时，便进行回溯，走到矩形右下角记录当前路径，并从所有可达路径中选出最小路径
2.  回溯条件 `if (row >= grid.length || col >= grid[0].length) {`：走到矩形外面需要进行回溯
3.  到达条件 `if (row == grid.length - 1 && col == grid[0].length - 1) {`：走到矩形右下角记录当前路径，并回溯

> 方法二：动态规划

1.  还是老问题：为什么使用动态规划呢？假如说我们现在正要从 `grid[row-1][col]` 或者 `grid[row1][col-1]` 走到 `grid[row][col]`，如果我们知道走到 `grid[row-1][col]` 和 `grid[row1][col-1]` 的最小路径，那么走到 `grid[row][col]` 的最小路径为 `dp[row][col] = Math.min(dp[row - 1][col] + grid[row][col], dp[row][col - 1] + grid[row][col]);`
2.  归根到底，我们还是要讲大问题化为子问题来求解，一步一步通过子问题递推处大问题的解，由于大问题需要用到子问题的结果，所以子问题的结果需要保存起来
3.  我们定义 `dp[row][col]` 的含义为：走到 `grid[row][col]` 所需的最短路径和，这样就好办了，直接利用状态转移方程就可求出走到 `grid[row][col]` 的最短路径和：`dp[row][col] = Math.min(dp[row - 1][col] + grid[row][col], dp[row][col - 1] + grid[row][col]);`

--------------------

边界问题：当 `row == 0` 或者当 `col == 0` 时，我们需要额外考虑

1.  第一种办法是在动态规划的 `for` 循环外面直接将 `dp[0][]` 和 `dp[][0]`求出来，因为第一行的单元格只能通过其左边的单元格向右迈一步到达，第一列的单元格只能通过其上面的单元格向下迈一步到达
2.  第二种办法是直接将对 `row == 0` 和 `col == 0` 的判断放在动态规划的 `for` 循环中，判断 `row` 能不能往上移动一格，如果不能则取 `lastRow = 0`，否则 `lastRow = row-1`，对于 `leftCol` 也是同样的道理，则上一步最短路径和为 `dp[lastRow][leftCol]`，然后再加上本次的路径 `grid[row][col]`，即为到达 `grid[row][col]` 的最短路径和

## 4、代码实现 ##

方法一：深度优先搜索，超出时间限制

class Solution {
        
        int mminPathSum = Integer.MAX_VALUE;
    
        public int minPathSum(int[][] grid) {
        
            dfs(grid, 0, 0, 0);
            return mminPathSum;
        }
    
        public void dfs(int[][] grid, int row, int col, int pathSum) {
        
            // 走到矩形外面需要进行回溯
            if (row >= grid.length || col >= grid[0].length) {
        
                return;
            }
            // 当前路径之和
            pathSum += grid[row][col];
            // 走到矩形右下角记录当前路径，并回溯
            if (row == grid.length - 1 && col == grid[0].length - 1) {
        
                mminPathSum = Math.min(pathSum, mminPathSum);
                return;
            }
            // 递归向下走
            dfs(grid, row + 1, col, pathSum);
            // 递归向右走
            dfs(grid, row, col + 1, pathSum);
        }
    }

方法二：动态规划

class Solution {
        
    
        public int minPathSum(int[][] grid) {
        
            int height = grid.length;
            int width = grid[0].length;
            int[][] dp = new int[height][width];
            // 动态规划：一行一行处理
            for (int row = 0; row < height; row++) {
        
                for (int col = 0; col < width; col++) {
        
                    int lastRow, leftCol;
                    // 如果 row == 0 或者 col == 0，则说明动态规划正处于第一行或者第一列，需进行特殊处理
                    if (row == 0 || col == 0) {
        
                        // row 能上移则上移，不能上移则取 0
                        lastRow = (row - 1 < 0) ? 0 : (row - 1);
                        // col 能左移则左移，不能左移则取 0
                        leftCol = (col - 1 < 0) ? 0 : (col - 1);
                        // 上一步最短路径和为 dp[lastRow][leftCol]
                        // 然后再加上本次的路径 grid[row][col]
                        // 即为到达 grid[row][col] 的最短路径和
                        dp[row][col] = dp[lastRow][leftCol] + grid[row][col];
                    } else {
        
                        // 否则，正常进行状态转移即可
                        // 要么从上面的单元格下来，要么从左边的单元格右移，取其较小值
                        dp[row][col] = Math.min(
                            dp[row - 1][col] + grid[row][col],
                            dp[row][col - 1] + grid[row][col]);
                    }
                }
            }
            return dp[height - 1][width - 1];
        }
    }