64. Minimum Path Sum

1.問題

• 尋找從左上角到右下角總和最小的路徑

2.想法

• 提問

• function header, parameter

• test input

• 說明想法

  • 動態規劃, 到每一點的途徑等於前一點(上面, 左邊)與自己的總和

  • 特例: 因為機器人只能往下面跟往右邊, 因此對最上方的row來說, 前一步不會來自上方, 對最左邊的column來說, 前一步不會來自左方

• 測試計算複雜度

3.程式碼

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.size() == 0) {
            return 0;
        }
        
        int m = grid.size();
        int n = grid[0].size();
        
        //dp: 每格的值 = min(上, 左) + 自己
        vector<vector<int>> minVal(m, vector<int>(n, 0));
        minVal[0][0] = grid[0][0];
        
        //bottom
        for (int i = 1; i < m; i++) {
            minVal[i][0] = minVal[i - 1][0] + grid[i][0];
        }
        
        //left
        for (int j = 1; j < n; j++) {
            minVal[0][j] = minVal[0][j - 1] + grid[0][j];
        }
        
        //middle
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                minVal[i][j] = min(minVal[i - 1][j], minVal[i][j - 1]) + grid[i][j];
            }
        }
        
        return minVal[m - 1][n - 1];
        
    }
};