1 題目描述


給定一個m x n的矩陣，找到一條從左上角到右下角的最小路徑和。每次只能向右或是向下移動，但是他中間有障礙物，所以要避開障礙物。

2 解法

這題與LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南的題目類似，如果你會做Leetcode-62-Unique Paths，這題也是一樣的概念，只是這題有障礙物，因此碰到障礙物就要記得把路徑設定為0。

2.1 Iterative

因為已經做過類似的題目，所以直接從Iterative下手，我的想法是這樣的：

  • 今天邊緣也有可能有障礙物，所以要從邊緣開始處理
  • 如果碰到障礙物，就把路徑設定為0
  • 其他的就是從上面或是左邊來的路徑和
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
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
    rows = len(obstacleGrid)
    columns = len(obstacleGrid[0])
    dp = [[0] * columns for _ in range(rows)]
    # 終點是1
    dp[rows-1][columns-1] = 1

    # 從終點到起點處理
    for row in range(rows - 1, -1, -1):
        for column in range(columns - 1, -1, -1):
            # 如果是障礙物，就設定為0
            if obstacleGrid[row][column] == 1:
                dp[row][column] = 0
            # 其他狀況，不處理終點的狀況下
            elif dp[row][column] == 0:
                down, left = 0, 0
                # 如果不是邊緣，就取下面的值，否則為0
                if row < rows-1 and dp[row+1][column] is not None:
                    down = dp[row+1][column]
                # 如果不是邊緣，就取左邊的值，否則為0
                if column < columns-1 and dp[row][column+1] is not None:
                    left = dp[row][column+1]
                dp[row][column] = down + left

    return dp[0][0]

這題也有一樣的思路，可以dp只用兩個row就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def uniquePathsWithObstacles2(self, obstacleGrid: List[List[int]]) -> int:
    rows = len(obstacleGrid)
    columns = len(obstacleGrid[0])
    # row 只有兩個
    dp = [[0] * columns for _ in range(2)]
    dp[0][columns-1] = 1

    for row in range(rows - 1, -1, -1):
        for column in range(columns - 1, -1, -1):
            if obstacleGrid[row][column] == 1:
                dp[0][column] = 0 # 會因為沒有使用deecopy影響到dp[1][column]
            elif not(row == rows-1 and column == columns-1):
                down, left = 0, 0
                if row < rows - 1 and dp[1][column] is not None:
                    down = dp[1][column]
                if column < columns - 1 and dp[0][column + 1] is not None:
                    left = dp[0][column + 1]
                dp[0][column] = down + left
        # 使用deepcopy才不會在修改dp[0]時影響到dp[1]
        dp[1] = copy.deepcopy(dp[0])

    return dp[0][0]

3 總結

這題不難，也是很快就寫出來了，只是在處理邊緣的時候要注意不要超過邊界，以及要處理障礙物的情況。這題的時間複雜度是O(n * m)，空間複雜度是O(n * m)。如果你想要優化空間複雜度，可以參考上面的解法，只用兩個row的空間就好。