当前位置：首页 > web >正文

【LeetCode 热题100】网格路径类 DP 系列题：不同路径最小路径和（力扣62 / 64 ）（Go语言版）

web 2025/6/24 21:42:25

🧭 网格路径类 DP 系列题：不同路径 & 最小路径和（LeetCode 62 / 64）

🧮 62. 不同路径（计算路径总数）
💰 64. 最小路径和（求路径最小代价）

🧮 62. 不同路径（Unique Paths）

📌 题目描述

一个机器人位于一个 m x n 网格左上角，只能向下或向右移动，每次一步。问有多少条不同路径可以走到右下角？

🧠 解题思路

这是一道经典的二维动态规划问题。

✅ 状态定义

dp[i][j] 表示走到第 i 行第 j 列的路径数量。

🔁 状态转移

机器人只能从上方或左方到达 (i,j)：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

🎯 初始条件

第一行 & 第一列都只有一条路径可达。

✅ Go 实现（二维 DP）

func uniquePaths(m int, n int) int {dp := make([][]int, m)for i := range dp {dp[i] = make([]int, n)dp[i][0] = 1}for j := 0; j < n; j++ {dp[0][j] = 1}for i := 1; i < m; i++ {for j := 1; j < n; j++ {dp[i][j] = dp[i-1][j] + dp[i][j-1]}}return dp[m-1][n-1]
}

💡 空间优化

由于每次只依赖上一行和当前行，可以用一维数组滚动更新：

func uniquePaths(m int, n int) int {dp := make([]int, n)for i := range dp {dp[i] = 1}for i := 1; i < m; i++ {for j := 1; j < n; j++ {dp[j] += dp[j-1]}}return dp[n-1]
}

💰 64. 最小路径和（Minimum Path Sum）

📌 题目描述

给定一个 m x n 的网格，每个单元格内有一个非负整数，求从左上角到右下角一条路径，使得路径上数字总和最小。

🧠 解题思路

与上一题相似，不过这题是求最小路径代价。

✅ 状态定义

dp[i][j] 表示走到 (i,j) 所需的最小路径和。

🔁 状态转移

只能从上方或左方来：

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

✅ Go 实现

func minPathSum(grid [][]int) int {m, n := len(grid), len(grid[0])dp := make([][]int, m)for i := range dp {dp[i] = make([]int, n)}dp[0][0] = grid[0][0]for i := 1; i < m; i++ {dp[i][0] = dp[i-1][0] + grid[i][0]}for j := 1; j < n; j++ {dp[0][j] = dp[0][j-1] + grid[0][j]}for i := 1; i < m; i++ {for j := 1; j < n; j++ {dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]}}return dp[m-1][n-1]
}func min(a, b int) int {if a < b {return a}return b
}

🔚 总结与对比

题目	目标	状态定义	转移逻辑	可否空间优化
62. 不同路径	统计路径条数	`dp[i][j]` 为到达 (i,j) 的路径数	`dp[i-1][j] + dp[i][j-1]`	✅ 可用一维数组优化
64. 最小路径和	求最小路径值	`dp[i][j]` 为到达 (i,j) 的最小和	`min(dp[i-1][j], dp[i][j-1]) + grid[i][j]`	✅ 可用一维数组优化