Problem: https://leetcode.com/problems/unique-paths-ii/description/

Accepted 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
25
26
27
28
29
30
31
32
33
34
35
36
37
"""
Time complexity: O(mn)
Space complexity: O(mn)
"""
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;   // 起點終點可以是障礙物，所以直接輸出為0種方式
        vector<vector<int>> dp(m, vector<int>(n, 0));
        // 初始化dp，一開始先全部設為零
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                    // 如果踢到鐵板，也就是目前搜到的格子是障礙物，則直接把可以通到那格的方法數設為零
                } else {
                    if (i == 0 && j == 0) {
                        dp[i][j] = 1;
                        // 起點的方法數是1
                    } else if (i == 0) {
                        dp[i][j] = dp[i][j - 1];
                        // 如果已經在最上邊，則方法只可能來自該格子的左邊
                    } else if (j == 0) {
                        dp[i][j] = dp[i - 1][j];
                        // 如果已經在最左邊，則方法只可能來自該格子的上邊
                    } else {
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                        // 如果在其餘位置，則方法數會來自於該格子左邊與上邊的相加
                    }
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# O(m*n) space
def uniquePathsWithObstacles1(self, obstacleGrid):
    if not obstacleGrid:
        return 
    r, c = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0 for _ in xrange(c)] for _ in xrange(r)]
    dp[0][0] = 1 - obstacleGrid[0][0]
    for i in xrange(1, r):
        dp[i][0] = dp[i-1][0] * (1 - obstacleGrid[i][0])
    for i in xrange(1, c):
        dp[0][i] = dp[0][i-1] * (1 - obstacleGrid[0][i])
    for i in xrange(1, r):
        for j in xrange(1, c):
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) * (1 - obstacleGrid[i][j])
    return dp[-1][-1]
    
# O(n) space
def uniquePathsWithObstacles2(self, obstacleGrid):
    if not obstacleGrid:
        return 
    r, c = len(obstacleGrid), len(obstacleGrid[0])
    cur = [0] * c
    cur[0] = 1 - obstacleGrid[0][0]
    for i in xrange(1, c):
        cur[i] = cur[i-1] * (1 - obstacleGrid[0][i])
    for i in xrange(1, r):
        cur[0] *= (1 - obstacleGrid[i][0])
        for j in xrange(1, c):
            cur[j] = (cur[j-1] + cur[j]) * (1 - obstacleGrid[i][j])
    return cur[-1]

# in place
def uniquePathsWithObstacles(self, obstacleGrid):
    if not obstacleGrid:
        return 
    r, c = len(obstacleGrid), len(obstacleGrid[0])
    obstacleGrid[0][0] = 1 - obstacleGrid[0][0]
    for i in xrange(1, r):
        obstacleGrid[i][0] = obstacleGrid[i-1][0] * (1 - obstacleGrid[i][0])
    for i in xrange(1, c):
        obstacleGrid[0][i] = obstacleGrid[0][i-1] * (1 - obstacleGrid[0][i])
    for i in xrange(1, r):
        for j in xrange(1, c):
            obstacleGrid[i][j] = (obstacleGrid[i-1][j] + obstacleGrid[i][j-1]) * (1 - obstacleGrid[i][j])
    return obstacleGrid[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
"""
Time complexity: O(mn)
Space complexity: O(mn)
"""
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        if(obstacleGrid[0][0]==1) return 0;
        if(obstacleGrid[m-1][n-1]==1) return 0;
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i=0;i<m;i++) {
            if(obstacleGrid[i][0]==1) break;
            dp[i][0]=1;
        }
        for(int i=0;i<n;i++) {
            if(obstacleGrid[0][i]==1) break;
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                if(obstacleGrid[i-1][j]==1 && obstacleGrid[i][j-1]==0) {
                    dp[i][j]=dp[i][j-1];
                } else if(obstacleGrid[i-1][j]==0 && obstacleGrid[i][j-1]==1) {
                    dp[i][j]=dp[i-1][j];
                } else if (obstacleGrid[i-1][j]==1 && obstacleGrid[i][j-1]==1) {
                    dp[i][j]=0;
                } else {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};