LeetCode 熱題 100 | 64. 最小路徑和

大家好，今天我們來解決一道經典的動態規劃問題——最小路徑和。這道題在 LeetCode 上被標記為中等難度，要求找到從網格的左上角到右下角的路徑，使得路徑上的數字總和為最小。

---

問題描述

給定一個包含非負整數的 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

---

解題思路

核心思想

1. 動態規劃：

   • 使用動態規劃（DP）來解決這個問題。
   • 定義 dp[i][j] 為從網格的左上角到達位置 (i, j) 的最小路徑和。
   • 狀態轉移方程為：
     [
     dp[i][j] = \min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
     ]
     其中，dp[i-1][j] 表示從上方到達 (i, j) 的最小路徑和，dp[i][j-1] 表示從左方到達 (i, j) 的最小路徑和。

2. 初始化：

   • dp[0][0] = grid[0][0]，因為從起點到起點的路徑和就是起點的值。
   • 第一行和第一列的所有位置只能從一個方向到達，因此初始化為累加值。

3. 遍歷：

   • 遍歷整個網格，根據狀態轉移方程更新 dp[i][j]。

---

Python代碼實現

class Solution:def minPathSum(self, grid):m, n = len(grid), len(grid[0])dp = [[0] * n for _ in range(m)]dp[0][0] = grid[0][0]# 初始化第一行for j in range(1, n):dp[0][j] = dp[0][j-1] + grid[0][j]# 初始化第一列for i in range(1, m):dp[i][0] = dp[i-1][0] + grid[i][0]# 遍歷網格for i in range(1, m):for j in range(1, n):dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]return dp[m-1][n-1]

代碼解析

1. 初始化：

   • dp 數組初始化為一個 m x n 的二維列表，所有值初始化為 0。
   • dp[0][0] = grid[0][0]，因為從起點到起點的路徑和就是起點的值。
   • 第一行和第一列的所有位置只能從一個方向到達，因此初始化為累加值。

2. 狀態轉移：

   • 遍歷從 (1, 1) 到 (m-1, n-1) 的每個位置 (i, j)。
   • 對于每個位置 (i, j)，更新 dp[i][j] 為 min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。

3. 返回結果：

   • 最終結果存儲在 dp[m-1][n-1] 中，表示從左上角到右下角的最小路徑和。

---

復雜度分析

• 時間復雜度：O(m * n)，其中 m 和 n 分別是網格的行數和列數。需要遍歷整個網格。
• 空間復雜度：O(m * n)，使用了大小為 m x n 的 dp 數組。

---

示例運行

示例 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

---

總結

通過動態規劃的方法，我們可以高效地解決最小路徑和問題。狀態轉移方程 dp[i][j] = \min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 確保了我們能夠找到從左上角到右下角的最小路徑和。希望這篇題解對大家有所幫助，如果有任何問題，歡迎在評論區留言討論！

關注我，獲取更多算法題解和編程技巧！