LeetCode 64. Minimum Path Sum [Medium] [C++] 解題筆記

題目給定一個 m x n 的 array 裡面填滿 "非零整數" 求從左上走到右下的路徑中沿路的權重和最小值。

這題和 62. Unique Paths 與 63. Unique Paths II 非常的類似，都是用同樣的 DP 方法求解。

EX:

  [1,3,1]
  [1,5,1]
  [4,2,1]

Ans: 7 ,  1->3->1->1->1

想法:

        與 62. Unique Paths 一樣，利用一維陣列紀錄當前的 row，然後在每個位置 P 時取 P 的左方一格與 P 的右方一格之中累積權重較小的路徑加上 P 的權重即是從左上到這個 P 的最小權重。

其實還有一種作法是不需要額外的一維陣列紀錄路徑權重，取而代之的是直接在 input 的 grid map上更新權重，好處是省空間，壞處是會修改到 input data 有時候比較不安全或不希望修改到 input data，就是一個取捨。

   

Time Complexity: O(m*n) time, O(n) space

完整程式碼:

class Solution {

public:

    int minPathSum(vector<vector<int>>& grid) {

        if (grid.empty()) { return 0; }

        vector<int> cur(grid[0].size());

        int up = 0;

        int left = 0;

        for (int i = 0; i < grid.size(); i++) {

            for (int j = 0; j < grid[i].size(); j++) {

                if (i == 0 && j == 0) {

                    cur[j] = grid[i][j];

                }

                else {

                    up = (i == 0)? INT_MAX : cur[j];

                    left = (j == 0)? INT_MAX : cur[j - 1];

                    cur[j] = grid[i][j] + min(up, left);

                }

            }

        }

        return cur[grid[0].size() - 1];

    }

};