leetcode 62 63 Unique Paths

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 | class Solution(object): |