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

简介: LeetCode 训练场:64. 最小路径和

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];
}
目录
相关文章
|
11月前
【LeetCode 35】112.路径总和
【LeetCode 35】112.路径总和
92 0
|
4月前
|
Go 开发者 索引
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。
254 14
|
5月前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
116 4
|
5月前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
135 10
|
11月前
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
87 0
|
11月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
83 0
|
存储 算法 Linux
LeetCode第71题简化路径
文章讲述了LeetCode第71题"简化路径"的解题方法,利用栈的数据结构特性来处理路径中的"."和"..",实现路径的简化。
LeetCode第71题简化路径
LeetCode第64题最小路径和
LeetCode第64题"最小路径和"的解题方法,运用动态规划思想,通过构建一个dp数组来记录到达每个点的最小路径和,从而高效求解。
LeetCode第64题最小路径和
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
198 4
|
存储 Python
【Leetcode刷题Python】滑雪路径消耗时间:Testing Round #16 (Unrated) C. Skier
Leetcode题目"Testing Round #16 (Unrated) C. Skier"的Python解决方案,题目要求计算给定滑雪路径字符串的总耗时,其中未走过的边耗时5秒,走过的边耗时1秒。
122 4