LeetCode 训练场：64. 最小路径和

村雨遥

发布于 2022-06-15 10:36:10

1670

发布于 2022-06-15 10:36:10

文章被收录于专栏：JavaPark

1. 题目

64. 最小路径和

2. 描述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。

3. 实现方法

3.1 方法 1

3.1.1 思路

动态规划，分三步：

要从左上角走到右下角，我们定义 dp[i][j] 为机器人走到 (i, j) 位置时最小的路径和，所以我们要的最终结果为 dp[m - 1][n - 1]，其中 m 为行数，n 为列数；
要走到 (i, j)，我们有两种方式：
- 从 (i - 1, j) 走一步；
- 从 (i, j - 1) 走一步；
而要保证最终结果最小，我们就可以取两者中的最小值加上当前网格值就是最终结果 dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1])
接着考虑边界初始值，毫无疑问起点要赋值，即 dp[0][0] = grid[i][j]，然后就是在最上行和最左列：
- 最上行，只能一直往左走，dp[0][j] = dp[0][j - 1] + grid[0][j]
- 最左列，只能一直往上走，dp[i][0] = dp[i - 1][0] + grid[i][0]

3.1.2 实现

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

    if(m <= 0 || n <= 0){
        return 0;
    }

    // 声明
    int[][] dp = new int[m][n];
    // 起点
    dp[0][0] = grid[0][0];

    // 最上行
    for(int i = 1; i < n; i++){
        dp[0][i] = dp[0][i - 1] + grid[0][i];
    }

    // 最左列
    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];
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-09-08，如有侵权请联系 cloudcommunity@tencent.com 删除