💢歡迎來到張胤塵的技術站
💥技術如江河，匯聚眾志成。代碼似星辰，照亮行征程。開源精神長，傳承永不忘。攜手共前行，未來更輝煌💥

官方站點： 力扣 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

🌺🌺🌺撒花！

如果本文對你有幫助，就點關注或者留個👍
如果您有任何技術問題或者需要更多其他的內容，請隨時向我提問。