每日一题：LeetCode-64. 最小路径和

作者：半亩房顶

2023-12-14
北京
本文字数：923 字
阅读完需：约 3 分钟

刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-path-sum/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个包含非负整数的 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

思路

这道题是道非常标准的动态规划题了

dp[i][j]含义就是到达此位置时的最小路径和

状态方程也很是好写

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

还有最后一个问题就是初始化，我们配合一个图来看下：

因为只能往下、往右走，那么没有上面元素的第一排，和没有左边元素的第一列，就是可以固定写出对应dp数组内容的地方了，初始化至此也就完成了，其余的元素，其上方和左方元素都可以推算而出了

基本上代码也就出来了

代码

func minPathSum(grid [][]int) int {    m := len(grid)    n := len(grid[0])
    // 初始化dp数组    dp := make([][]int, m)    for k, _ := range dp {        dp[k] = make([]int, n)        // 初始化第一排        if k == 0 {            for l, _ := range dp[k] {                if l == 0 {                    dp[k][l] = grid[k][l]                } else {                    dp[k][l] = grid[k][l] + dp[k][l-1]                }            }        } else {            // 初始化第一列            dp[k][0] = grid[k][0] + dp[k-1][0]        }    }
    // 求解    // 也可以把初始化和后续位置求解放到一个循环，但是感觉这样会更清晰些    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 b    }    return a}