【经典算法】LeetCode 64. 最小路径和(Java/C/Python3/Golang实现含注释说明,Easy)

embedded/2024/10/15 13:27:48/

  • 作者主页： 🔗进朱者赤的博客

  • 精选专栏：🔗经典算法

  • 作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）

  • ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论，💬支持博主，记得点个大大的关注，持续更新🤞
    ————————————————-

文章目录

  • 题目描述
  • 思路及实现
    • 方式一：动态规划（朴素DP ）
      • 思路
      • 代码实现
        • Java版本
        • C语言版本
        • Python3版本
        • go
      • 复杂度分析
    • 方式二：滚动数组优化DP
      • 思路
      • 代码实现
        • Java版本
        • C语言版本
        • Python3版本
        • go
      • 复杂度分析
  • 总结
  • 相似题目

  • 标签(题目类型)：动态规划

题目描述

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

在这里插入图片描述

说明：每次只能向下或者向右移动一步。示例 1：输入：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] <= 200

原题：LeetCode 64.最小路径和

思路及实现

方式一：动态规划（朴素DP ）

思路

可以使用动态规划来求解最小路径和。

要求从左上角转移到右下角的最小路径和，每次只能往右走或者往下走。换句话说，对于位置 (i, j)，其只能从 (i-1, j) 和 (i, j-1) 两个位置转移而来。我们设 dp[i][j] 表示到达位置 (i, j) 的最小路径和。
那么 dp[i][j] 肯定要从 dp[i-1][j] 和 dp[i][j-1] 中那个更小的状态转移过来，
因此状态转移方程为：dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]。
在这里插入图片描述
边界条件：

  • 当 i = 0, j = 0 时，即左上角位置，其左侧和上侧单元格都不存在，dp[0][0] = grid[0][0]；
  • 当 i = 0, j ≠ 0 时，即首行元素，其上侧单元格不存在，dp[0][j] = dp[0][j-1] + grid[0][j];
  • 当 i ≠ 0, j = 0 时，即首列元素，其左侧单元格不存在，dp[i][0] = dp[i-1][0] + grid[i][0];

代码实现

Java版本
java">public class Solution {public int minPathSum(int[][] grid) {if (grid == null || grid.length == 0 || grid[0].length == 0) {return 0;}int m = grid.length;int n = grid[0].length;int[][] dp = new int[m][n];// 初始化第一行和第一列//初始化第一个元素dp[0][0] = grid[0][0];// 初始化第一行for (int i = 1; i < m; i++) {dp[i][0] = dp[i - 1][0] + grid[i][0];}// 初始化第一列for (int j = 1; j < n; j++) {dp[0][j] = dp[0][j - 1] + grid[0][j];}// 填充其他位置for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}// 最后一个元素即结果return dp[m - 1][n - 1];}
}

说明：
此解法使用动态规划，时间复杂度为 O(mn)，空间复杂度也为 O(mn)。

C语言版本
#include <stdio.h>
#include <limits.h>int minPathSum(int** grid, int gridSize, int* gridColSize){if (grid == NULL || gridSize == 0 || gridColSize[0] == 0) {return 0;}int m = gridSize;int n = gridColSize[0];int** dp = (int**)malloc(m * sizeof(int*));for (int i = 0; i < m; i++) {dp[i] = (int*)malloc(n * sizeof(int));}// 初始化第一行和第一列dp[0][0] = grid[0][0];for (int i = 1; i < m; i++) {dp[i][0] = dp[i - 1][0] + grid[i][0];}for (int j = 1; j < n; j++) {dp[0][j] = dp[0][j - 1] + grid[0][j];}// 填充其他位置for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = (dp[i - 1][j] < dp[i][j - 1]) ? (dp[i - 1][j] + grid[i][j]) : (dp[i][j - 1] + grid[i][j]);}}int result = dp[m - 1][n - 1];// 释放动态分配的内存for (int i = 00; i < m; i++) {free(dp[i]);}free(dp);return result;
}int main() {// 示例网格int gridSize = 3;int gridColSize[3] = {3, 3, 3};int grid[3][3] = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};int** gridPtr = (int**)malloc(gridSize * sizeof(int*));for (int i = 0; i < gridSize; i++) {gridPtr[i] = grid[i];}int minSum = minPathSum(gridPtr, gridSize, gridColSize);printf("The minimum path sum is: %d\n", minSum);// 释放动态分配的内存free(gridPtr);return 0;
}

说明：
C语言版本同样使用动态规划，时间复杂度和空间复杂度与Java版本相同。注意在C语言中需要手动管理内存，因此在函数结束时需要释放动态分配的内存。

Python3版本
def minPathSum(grid):if not grid or not grid[0]:return 0m, n = len(grid), len(grid[0])dp = [[0] * n for _ in range(m)]# 初始化第一行和第一列dp[0][0] = grid[0][0]for i in range(1, m):dp[i][0] = dp[i - 1][0] + grid[i][0]for j in range(1, n):dp[0][j] = dp[0][j - 1] + grid[0][j]# 填充其他位置for i in range(1, m):for j in range(1, n):dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]return dp[m - 1][n - 1]# test
# 示例网格
grid = [[1, 3, 1],[1, 5, 1],[4, 2, 1]
]min_sum = minPathSum(grid)
print(f"The minimum path sum is: {min_sum}")

说明：
Python3版本使用动态规划，简洁易懂。由于Python中的列表支持动态大小，因此不需要手动管理内存。

go_205">go
go">// minPathSum 使用朴素DP方法求解最小路径和
func minPathSum(grid [][]int) int {if len(grid) == 0 || len(grid[0]) == 0 {return 0}rows, cols := len(grid), len(grid[0])// 创建一个二维DP数组，大小与grid相同，用于存储到达每个位置的最小路径和dp := make([][]int, rows)for i := range dp {dp[i] = make([]int, cols)}// 初始化第一行和第一列dp[0][0] = grid[0][0]for i := 1; i < rows; i++ {dp[i][0] = dp[i-1][0] + grid[i][0] // 第一列的最小路径和依赖于上一行的值}for j := 1; j < cols; j++ {dp[0][j] = dp[0][j-1] + grid[0][j] // 第一行的最小路径和依赖于前一列的值}// 填充剩余的DP数组for i := 1; i < rows; i++ {for j := 1; j < cols; j++ {// 当前位置的最小路径和取上方和左方位置的最小路径和加上当前位置的值dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]}}// 返回右下角位置的最小路径和return dp[rows-1][cols-1]
}// min 返回两个整数中的较小值
func min(a, b int) int {if a < b {return a}return b
}// 示例使用
func main() {grid := [][]int{{1, 3, 1},{1, 5, 1},{4, 2, 1},}minSum := minPathSum(grid)fmt.Printf("The minimum path sum is: %d\n", minSum)
}

说明：
minPathSum：使用朴素DP算法计算从grid左上角到右下角的最小路径和。
逻辑步骤

  1. 初始化二维DP数组dp，大小与grid相同。
  2. 填充dp数组的第一行和第一列。
  3. 遍历grid剩余元素，根据状态转移方程填充dp数组。
  4. 返回dp数组的右下角元素作为结果。

复杂度分析

  • 时间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。需要遍历每个网格位置一次。
  • 空间复杂度：O(mn)，需要一个二维数组 dp 来存储每个位置的最小路径和。

方式二：滚动数组优化DP

对于上述的动态规划解法，我们注意到在计算 dp[i][j] 时，只依赖于其正上方和左方的值。因此，我们可以使用滚动数组来优化空间复杂度，将空间复杂度从 O(mn) 降低到 O(n)。

思路

由于每一行的计算只依赖于上一行的值，我们可以只保留上一行的值，并在当前行上直接计算。这样，我们只需要一个一维数组来存储上一行的值即可。

代码实现

Java版本
java">public int minPathSum(int[][] grid) {if (grid == null || grid.length == 0 || grid[0].length == 0) {return 0;}int m = grid.length;int n = grid[0].length;int[] dp = new int[n];// 初始化第一行dp[0] = grid[0][0];for (int j = 1; j < n; j++) {dp[j] = dp[j - 1] + grid[0][j];}// 填充其他行for (int i = 1; i < m; i++) {int prev = dp[0]; // 保存上一行的第一个值，因为下一个dp[0]会被覆盖for (int j = 0; j < n; j++) {int curr = dp[j]; // 保存当前位置的值，因为下一个dp[j]会被覆盖if (j == 0) {// 如果是第一列，则只能从上方来dp[j] = prev + grid[i][j];} else {// 否则取上方和左方的最小值dp[j] = Math.min(prev, dp[j]) + grid[i][j];}prev = curr; // 更新prev为下一个位置的上一行值}}// dp数组的最后一个元素即为最小路径和return dp[n - 1];
}
C语言版本
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>int minPathSum(int** grid, int gridSize, int* gridColSize) {if (grid == NULL || gridSize == 0 || gridColSize[0] == 0) {return 0;}int n = gridColSize[0];int* dp = (int*)malloc(n * sizeof(int));if (dp == NULL) {return -1;}// 初始化第一行dp[0] = grid[0][0];for (int j = 1; j < n; j++) {dp[j] = dp[j - 1] + grid[0][j];}// 填充其他行for (int i = 1; i < gridSize; i++) {int prev = dp[0]; // 保存上一行的第一个值for (int j = 0; j < n; j++) {int temp = dp[j]; // 临时保存当前位置的值if (j == 0) {dp[j] = prev + grid[i][j];} else {dp[j] = (prev < dp[j]) ? (prev + grid[i][j]) : (dp[j] + grid[i][j]);}prev = temp; // 更新prev}}int result = dp[n - 1];free(dp);return result;
}int main() {int gridSize = 3;int gridColSize[3] = {3, 3, 3};int grid[3][3] = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};int** gridPtr = (int**)malloc(gridSize * sizeof(int*));for (int i = 0; i < gridSize; i++) {gridPtr[i] = (int*)malloc(gridColSize[i] * sizeof(int));for (int j = 0; j < gridColSize[i]; j++) {gridPtr[i][j] = grid[i][j];}}int minSum = minPathSum(gridPtr, gridSize, gridColSize);printf("The minimum path sum is: %d\n", minSum);// 释放动态分配的内存for (int i = 0; i < gridSize; i++) {free(gridPtr[i]);}free(gridPtr);return 0;
}
Python3版本
def minPathSum(grid):if not grid or not grid[0]:return 0m, n = len(grid), len(grid[0])dp = [0] * n# 初始化第一行dp[0] = grid[0][0]for j in range(1, n):dp[j] = dp[j - 1] + grid[0][j]# 填充其他行for i in range(1, m):prev = dp[0]for j in range(n):curr = dp[j]dp[j] = prev + grid[i][j] if j == 0 else min(prev, dp[j]) + grid[i][j]prev = currreturn dp[n - 1]# 示例网格
grid = [[1, 3, 1],[1, 5, 1],[4, 2, 1]
]min_sum = minPathSum(grid)
print(f"The minimum path sum is: {min_sum}")
go_421">go
go">// minPathSumOpt 使用滚动数组优化DP方法求解最小路径和
func minPathSumOpt(grid [][]int) int {if len(grid) == 0 || len(grid[0]) == 0 {return 0}rows, cols := len(grid), len(grid[0])// 只需要一个一维数组来保存当前行的最小路径和prevRow := make([]int, cols)currRow := make([]int, cols)// 初始化第一列prevRow[0] = grid[0][0]for j := 1; j < cols; j++ {prevRow[j] = prevRow[j-1] + grid[0][j]}// 填充剩余的行for i := 1; i < rows; i++ {// 交换prevRow和currRow，currRow用于保存当前行的最小路径和prevRow, currRow = currRow, prevRow// 初始化当前行的第一列currRow[0] = prevRow[0] + grid[i][0]// 填充当前行的剩余列for j := 1; j < cols; j++ {// 当前位置的最小路径和取上方和左方位置的最小路径和加上当前位置的值currRow[j] = min(prevRow[j], currRow[j-1]) + grid[i][j]}}// 返回最后一行的最后一个元素，即最小路径和return currRow[cols-1]
}// min 返回两个整数中的较小值
func min(a, b int) int {if a < b {return a}return b
}// 示例使用
func main() {grid := [][]int{{1, 3, 1},{1, 5, 1},{4, 2, 1},
}
minSum := minPathSumOpt(grid)
fmt.Printf("The minimum path sum with rolling array optimization is: %d\n", minSum)
}

说明：
函数功能
minPathSumOpt：使用滚动数组优化DP算法计算从grid左上角到右下角的最小路径和。
步奏

  1. 初始化两个一维数组prevRow和currRow。
  2. 填充prevRow数组作为第一行的最小路径和。
  3. 遍历grid剩余行，交替使用prevRow和currRow计算最小路径和。
  4. 返回currRow的最后一个元素作为结果。

复杂度分析

  • 时间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。仍然需要遍历每个网格位置一次。
  • 空间复杂度：O(n)，其中 n 是网格的列数。使用滚动数组只需要存储一行的值。

滚动数组优化后的空间复杂度更低，但时间复杂度保持不变。这种优化在处理大规模网格时尤其有用，因为它显著减少了内存的使用。

总结

解法思路特点优点缺点时间复杂度空间复杂度
朴素DP填充DP表，状态转移每个位置的状态取决于上方和左方直观易懂空间占用大O(mn)O(mn)
滚动数组优化DP只用一维数组，通过循环更新节省空间，利用上一行的值节省空间编程稍微复杂O(mn)O(n)

相似题目

相似题目难度链接
leetcode 349 两个数组的交集简单力扣-349
leetcode 62 不同路径中等力扣-62
leetcode 63 不同路径 II中等力扣-63
leetcode 64 最小路径和中等力扣-64
leetcode 120 三角形最小路径和中等力扣-120
leetcode 152 乘积最大子数组中等力扣-152
leetcode 198 打家劫舍中等力扣-198
leetcode 213 打家劫舍 II困难力扣-213
leetcode 300 最长递增子序列中等力扣-300
leetcode 309 最佳买卖股票时机含冷冻期中等力扣-309

这些题目都涉及到动态规划的思想，有些题目可能需要使用滚动数组进行优化，有些题目则需要根据特定条件调整状态转移方程。通过练习这些题目，可以加深对动态规划的理解和掌握。

在这里插入图片描述

欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界

  • 关于我：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等

  • —⬇️欢迎关注下面的公众号：进朱者赤，认识不一样的技术人。⬇️—


http://www.ppmy.cn/embedded/1794.html

相关文章

【ElasticSearch】安装（bug篇）

【ElasticSearch】安装（bug篇）

以下解决办法参考自网友们的分享 1. JDK绑定问题 但其实这样也没有问题&#xff0c;因为内嵌的jdk版本与当前的es版本是适配的 但是&#xff0c;如果内嵌的jdk与当前es不适配&#xff0c;那就要修改配置文件 / 添加环境变量&#xff0c;让es启动的时候能扫描到我们本地的jdk …
阅读更多...
已解决java.net.NoRouteToHostException: 无法到达主机异常的正确解决方法，亲测有效！！！

已解决java.net.NoRouteToHostException: 无法到达主机异常的正确解决方法，亲测有效！！！

已解决java.net.NoRouteToHostException: 无法到达主机异常的正确解决方法&#xff0c;亲测有效&#xff01;&#xff01;&#xff01; 目录 问题分析 报错原因 解决思路 解决方法 检查网络连接 核实目标地址 检查防火墙和路由器规则 验证VPN/代理设置 修正网络配置 …
阅读更多...
算法库应用-有序单链表插入节点

算法库应用-有序单链表插入节点

学习源头: 模仿贺利坚老师单链表排序文章浏览阅读5.9k次。　　本文针对数据结构基础系列网络课程(2)&#xff1a;线性表中第11课时单链表应用举例。例&#xff1a;拆分单链表 &#xff08;linklist.h是单链表“算法库”中的头文件&#xff0c;详情单击链接…&#xff09;//本程…
阅读更多...
工业级POE交换机的ACL

工业级POE交换机的ACL

工业级POE交换机通常支持访问控制列表&#xff08;Access Control List&#xff0c;ACL&#xff09;功能&#xff0c;用于实施网络安全策略。ACL可以根据源IP地址、目标IP地址、传输协议、端口号等条件来过滤和控制网络流量。 通过配置ACL&#xff0c;可以实现以下功能&#xf…
阅读更多...
docker 容器迁移

docker 容器迁移

目录 1、将容器打成镜像后迁移 2、导出和导入容器 1、将容器打成镜像后迁移 &#xff08;1&#xff09;将容器打成镜像 # 打成镜像 mycentos docker commit -m "my centos" -a "author" 2d1fba0978 mycentos # 打成镜像 mycentos&#xff0c;tag …
阅读更多...
如何花少量的钱举办一场漂亮的知识竞赛

如何花少量的钱举办一场漂亮的知识竞赛

如果预算不多&#xff0c;是不是就不能办出一场漂亮的知识竞赛活动了呢。我看未必&#xff0c;大家可以从以下几个方面去考虑。 一、降低场地费用 知识竞赛活动的费用大头是场地及配套设备&#xff08;大屏、音响、灯光、舞台等&#xff09;&#xff0c;先要考虑如何省去或减…
阅读更多...
MySQL 锁机制全面解析

MySQL 锁机制全面解析

目录 1. MySQL的锁类型1.1 全局锁1.2 表锁1.3 行锁1.4 共享锁&#xff08;读锁&#xff09;1.5 排它锁&#xff08;写锁&#xff09;1.6 死锁 2 乐观锁和悲观锁2.1 乐观锁2.2 悲观锁 3 意向锁4 间隙锁5 临键锁6. 事务隔离级别对锁的影响6.1 读未提交&#xff08;Read Uncommitt…
阅读更多...
ASP.NET基于BS方式的即时通讯软件的设计与实现

ASP.NET基于BS方式的即时通讯软件的设计与实现

摘 要 即时通讯&#xff08;Instant Messaging&#xff09;是目前Internet上最为流行的通讯方式&#xff0c;而各种各样的即时通讯软件也层出不穷&#xff1b;服务提供商也提供了越来越丰富的通讯服务功能。随着互联网的发展&#xff0c;即时通讯的运用将日益广泛&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023