# 64. Minimum Path Sum

## 1.問題

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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LN9kS56G2KEDfSdKvID%2F-LN9hNIUaCi1cSohJSGN%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-24%20%E4%B8%8B%E5%8D%884.32.26.png?alt=media\&token=23aac230-8b10-4173-85a7-6850500625d8)

## 2.想法

* 提問
* function header, parameter
* test input
* 說明想法&#x20;
  * 動態規劃, 到每一點的途徑等於前一點(上面, 左邊)與自己的總和
  * 特例: 因為機器人只能往下面跟往右邊, 因此對最上方的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];
        
    }
};
```
