runtime 0 ms, beats 100% of cpp submissions
O(mn) solution with explanation

tags: dp

Unique Paths II

📖 description

給定一個 2 維陣列，數值 0 表示可以通過的路，數值 1 表示有障礙物，請求從 (0,0) 至 (m,n) 在繞開障礙物時有多少種到達的可能。

ex.
    Input: 
        obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

    Output: 2
    
    Explanation: 
        There is one obstacle in the middle of the 3x3 grid above.
        There are two ways to reach the bottom-right corner:
        1. Right -> Right -> Down -> Down
        2. Down -> Down -> Right -> Right

🧠 solution

與前一題的方法不同，因為障礙物的存在，沒辦法使用數學的方法計算，於是必須利用 prefix sum 來累加可能性，不計算以及累加障礙物的格子。

⏳ time complexity

計算 2 維前綴和，時間複雜度 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 ans=0;
    int m,n;
    int uniquePathsWithObstacles(vector<vector<int>>& g) {
        m=g.size();
        n=g[0].size();
        if(g[0][0]==1) return 0;
        vector<vector<int>> path(m,vector<int>(n,0));
        path[0][0]=1;
        for(int x=0;x<m;x++){
            for(int y=0;y<n;y++){
                if(g[x][y]==1) continue;    // 遇到障礙物
                if(x>0 && y>0)
                    path[x][y]=path[x-1][y]+path[x][y-1];   // 從上方及左方走下來
                else if(x==0 && y>0)
                    path[x][y]=path[x][y-1];
                else if(x>0 && y==0)
                    path[x][y]=path[x-1][y];
            }
        }
        return path[m-1][n-1];
    }
};