Problem :

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1 :

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2 :

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

核心思維 :

1. 獲取行列數，創建二維陣列並設定起點
2. 初始化第一列，從上到下累加
3. 初始化第一行，從左至右累加
4. 計算所有位置的最小路徑和，每次計算取上方或左右的最小值再加上當前的值
5. 回傳右下角的路徑和

程式碼 :

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //獲取行列數
        int m = grid.size();
        int n = grid[0].size();
        //創建二維陣列並設定起點
        std::vector<std::vector<int>> dp(m, std::vector<int>(n)); 
        dp[0][0] = grid[0][0];
        //初始化第一列，從上到下累加
        for(int i = 1; i < m; i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        //初始化第一行，從左至右累加
        for(int j = 1; j < n; j++){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        //計算每個位置的最小路徑和
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                //取上方或左右的最小值，再加上當前的值
                dp[i][j] = std::min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        //回傳右下角的最小路徑和
        return dp[m-1][n-1];
    }
};

結論 :

這題的目標是用題目從給定的二維陣列的計算左上角到右下角的最小路徑和。首先獲取陣列的行數和列數，然後創建一個二維陣列dp來儲存每個位置的最小路徑和，起點dp[0][0]設為陣列的左上角值，接著對於第一列和第一行，分別累加上方和左方的值，以確保正確計算這些邊界位置的最小路徑和。從第二行第二列開始，對每個位置dp[i][j]計算其上方和左方的最小路徑和，並加上當前位置的值。這樣可以保證每個位置的值代表該點的最小路徑和，最後回傳最小路徑和。這個解題方式的時間複雜度為O(mn)，空間複雜度也是O(mn)，適用於處理相似的最小路徑和問題。