leetcode 62 63 Unique Paths
z

62. Unique Paths I


给定一个m*n的棋盘,从棋盘左上角到棋盘右下角最多有多少条路径。

每一次移动,只能向右移一格或者向下移动一格。

star
end

动态规划问题:

dp[i][j] = dp[i-1][j] + dp[i][j-1];

当i==0,或者j == 0时,表示在棋盘的边缘,只有向下或者向右一条路。所以dp[i][j] = 1;

63 Unique Path II


相对于上一题,增加了一个条件:给定了一个等棋盘大小的01矩阵,1表示对应位置为一个障碍位置,不能走。

同样求一共有多少条路。

start 1 0
0 0 0
0 0 0
0 1 end

当obstacleGird[i][j] == 1时,dp[i][j] = 0;

当i==0 and j==0时,dp[i][j] = 1;

当i==0时,dp[i][j] = dp[i][j-1]

当j==0时,dp[i][j] = dp[i-1][j]

dp[i][j] = dp[i-1][j] + dp[i][j-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
if not obstacleGrid or not obstacleGrid[0]:
return False
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [[0 for i in range(n)] for j in range(m)]
for i in range(m):
for j in range(n):
if obstacleGrid[i][j] == 0:
if i==0 and j==0:
dp[i][j] = 1
elif i==0:
dp[i][j] = dp[i][j-1]
elif j==0:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]