runtime 7 ms, beats 97.06% of cpp submissions
O(mn) solution with explanation

tags: dp

Minimum Path Sum

📖 description

給定一個 2 維陣列，元素內容為經過這格路的花費，請求從 (0,0) 到 (m,n) 最少的花費。
只能向右或是下走。

ex.
    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.

🧠 solution

乍看一下可以使用 dfs 求出每條從 (0,0) 到 (m,n) 路線的花費，取最小即可，而後續也能使用 dp 減少計算過的狀態。
但題目要求我們只能往右以及下移動，這個限制簡化了題目，我們只需要在原本的陣列上模擬一次即可，每個座標都可以從他的左或上方來到達，不斷取最小花費的方向，就可以維護最小花費到終點。

⏳ time complexity

遍歷一次陣列，時間複雜度為 O(mn) ，其中 m, n 表示陣列的大小。
總時間複雜度 O(mn)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minPathSum(vector<vector<int>>& g) {
        int m = g.size();
        int n = g[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 && j==0){
                    continue;
                }
                else if(i==0){
                    g[i][j] += g[i][j-1];   // 只能從上方到達
                }
                else if(j==0){
                    g[i][j] += g[i-1][j];   // 只能從左方到達
                }
                else{
                    g[i][j] += min(g[i-1][j],g[i][j-1]);    // 維護從左或上到達的最小花費
                }
            }
        }
        return g[m-1][n-1];
    }
};