DAY 25
2
Software Development

## [Day 25] 從LeetCode學演算法 - 0063. Unique Paths II (Medium)

``````Question:
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?
``````

``````An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.
``````
``````Example 1:
Input:
[
[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
``````

1. 能到達該點的方法數為0(已經是障礙物了)
2. 承1，因此對1個點來說，加總的方式應該是先看這個點是否是障礙物
不是的話，才需要考慮它左邊上面是否有可以到達的方法數。

(加到左邊或上面是障礙物的點沒關係，因為它已經是0了)

Java:

``````class Solution {
public int uniquePathsWithObstacles(int[][] obs) {
if (obs == null || obs[0][0] == 1) return 0;
int m = obs.length;
int n = obs[0].length;
int[][] res = new int[m][n];
res[0][0] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (obs[i][j] != 1) {
if (i - 1 >= 0) res[i][j] += res[i - 1][j];
if (j - 1 >= 0) res[i][j] += res[i][j - 1];
}
}
}
return res[m - 1][n - 1];
}
}
``````

Python的部分要特別留意二維列表的生成，

(第一層不會，因為0的部分還是基本型態而非物件)
(也就是動其中一個row會同步改到其他的row)

(實測上兩者速度並無明顯差異)

Python:

``````class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
if not obstacleGrid or obstacleGrid[0][0] == 1: return 0
m, n = len(obstacleGrid), len(obstacleGrid[0])
res = [[0]*n for _ in range(m)]
res[0][0] = 1
for i in range(m):
for j in range(n):
if obstacleGrid[i][j] != 1:
if i-1 >= 0:
res[i][j] += res[i-1][j]
if j-1 >= 0:
res[i][j] += res[i][j-1]

return res[-1][-1]
``````

「時間/空間複雜度？」
(O(mn), O(mn)，因我們會遍歷整個二維列表，

0283. Move Zeroes (Easy)