🧭 网格路径类 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] |
✅ 可用一维数组优化 |
✏️ 思维延伸
如果想更进一步，可以尝试：
-
- 不同路径 II（加上障碍）
-
- 三角形最小路径和（从底向上 DP）
-
- 下降路径最小和（支持斜着走）
这类问题的关键在于：
✅ 明确“状态”
🔁 写出“转移”
🎯 找准“边界”
