算法每日一练 (9)

💢欢迎来到张胤尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥

官方站点： 力扣 Leetcode

算法每日一练 (9)

最小路径和

题目地址：最小路径和

题目描述

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

解题思路

• 首先根据题目要求判断边界条件，当 m == n == 1 时，不需要任何处理，直接返回即可。

• 由题意可知，在矩阵中任何一个节点只有一种方式可到达：从左边或上边，那么假设 i 是矩阵的横坐标，j 是矩阵的纵坐标，则有如下规则：

  • 当 i == 0 并且 j == 0 时，就是 (0,0) 点，到达当前位置的路径最小和满足如下公式：
    $$tmp[i][j]=grid[i][j]$$
  • 当 i == 0 时，只能从左边到达，到达当前位置的路径最小和满足如下公式：
    $$tmp[i][j]=grid[i][j]+tmp[i][j-1]$$
  • 当 j == 0 时， 只能从上面到达，到达当前位置的路径最小和满足如下公式：
    $$tmp[i][j]=grid[i][j]+tmp[i-1][j]$$
  • 当 i != 0 并且 j != 0 时，到达当前位置的路径最小和满足如下公式：
    $$tmp[i][j]=grid[i][j]+min(tmp[i-1][j],tmp[i][j-1])$$

• 创建临时矩阵 tmp，根据以上的公式依次给矩阵中的每个元素赋值。

• 返回 tmp[m-1][n-1] 的值，因为 tmp[m-1][n-1] 存储的是就是到达右下角的最小路径和。

golang 的解法采用了上述的解题思路；c/c++ 和 lua 的解法采用了一维数组作为临时容器，感兴趣的同学可以作为参考。

解题代码

c/c++

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();if (m == 1 && n == 1)return grid[0][0];std::vector<int> tmp;tmp.resize(n);for (int j = 0; j < n; j++) {if (j == 0)tmp[j] = grid[0][j];elsetmp[j] = grid[0][j] + tmp[j - 1];}for (int i = 1; i < m; i++) {for (int j = 0; j < n; j++) {if (j == 0)tmp[j] += grid[i][j];elsetmp[j] = grid[i][j] + std::min(tmp[j - 1], tmp[j]);}}return tmp[n - 1];}
};

golang

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

lua

local function minPathSum(grid)local m, n = #grid, #grid[1]if m == 1 and n == 1 thenreturn grid[1][1]endlocal tmp = {}for j = 1, n doif j == 1 thentmp[j] = grid[1][j]elsetmp[j] = grid[1][j] + tmp[j - 1]endendfor i = 2, m dofor j = 1, n doif j == 1 thentmp[j] = tmp[j] + grid[i][j]elsetmp[j] = grid[i][j] + math.min(tmp[j], tmp[j - 1])endendendreturn tmp[n]
end

🌺🌺🌺撒花！

如果本文对你有帮助，就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容，请随时向我提问。