64. 最小路徑和https://leetcode.cn/problems/minimum-path-sum/description/

給定一個包含非負整數的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]表示：到達[i, j]位置處，最小路徑和是多少。

推導狀態轉移方程：要想到達[i, j]位置，只有2種情況：

• 先到達[i - 1, j]位置，再向下走一步，到達[i, j]位置。此時的最小路徑和就等于，到達[i - 1, j]位置的最小路徑和加上網格中[i, j]位置的值，即dp[i - 1][j] + grid[i][j]。
• 先到達[i, j - 1]位置，再向右走一步，到達[i, j]位置。此時的最小路徑和就等于，到達[i, j - 1]位置的最小路徑和加上網格中[i, j]位置的值，即dp[i][j - 1] + grid[i][j]。

到達[i, j]位置的最小路徑和，應該等于這兩種情況的較小值，即dp[i][j] = min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]) = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]。

初始化：觀察狀態轉移方程，我們發現，在計算dp表最上面一行和最左邊一列的值時，會出現越界訪問，所以我們要對其初始化。這里我們用增加輔助結點的方式來初始化。我們在dp表的最上面和最左邊分別加上一行一列輔助結點。接著，我們要考慮，如何初始化輔助結點，才能確保后續的填表是正確的。我們先把此時的dp表畫出來：

* * * *
* ? ? ?
* ?

不難意識到，左上角的?位置的值就應該是網格左上角的值。再根據狀態轉移方程，我們只需要讓min(dp[i - 1][j], dp[i][j - 1])這一項等于0，就能符合預期。所以，我們只需要讓左上角的?位置，它的上面和左邊2個*位置的值初始化為0即可。

* 0 * *
0 ? ? ?
* ?

接下來考慮除了左上角的?位置之外，其他的?位置的值。為了讓這些?位置的值符合預期，我們就要讓min(dp[i - 1][j], dp[i][j - 1])這一項中，*位置的值不影響結果。所以，我們要把這些*都初始化為+∞。由于并沒有導致溢出風險的運算，用INT_MAX代表+∞即可。

綜上所述：我們要在dp表的最上面和最左邊分別加上一行一列輔助結點，并且把[0, 1]位置和[1, 0]位置初始化為0，其余輔助結點初始化為INT_MAX。

填表順序：根據狀態轉移方程，dp[i][j]依賴于dp[i - 1][j]和dp[i][j - 1]這2項，所以應從上往下，從左往右填表。

返回值：根據狀態表示，顯然應返回dp表右下角的值，即dp[m][n]，對應到達網格右下角的最小路徑和。

細節問題：由于新增了一行一列輔助結點，所以dp表的規模比網格的規模大一行一列，即dp表的規模為(m + 1) x (n + 1)。由于添加了輔助結點，要時刻注意下標的映射關系，dp表的[i, j]位置對應網格的[i - 1, j - 1]位置。

時間復雜度：O(m x n)，空間復雜度：O(m x n)。

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();// 創建dp表vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));// 初始化dp[0][1] = dp[1][0] = 0;// 填表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];}}// 返回結果return dp[m][n];}
};