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

🧭 网格路径类 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
}

🔚 总结与对比

✏️ 思维延伸

如果想更进一步，可以尝试：

• 63. 不同路径 II（加上障碍）
• 120. 三角形最小路径和（从底向上 DP）
• 931. 下降路径最小和（支持斜着走）

这类问题的关键在于：

✅ 明确“状态”
🔁 写出“转移”
🎯 找准“边界”