LeetCode 62. 不同路径

力扣题目链接

class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = [[1] * n for _ in range(m)]for j in range(n):for i in range(m):if i == 0 and j > 0:dp[i][j] = dp[i][j-1]elif i > 0 and j == 0:dp[i][j] = dp[i-1][j]elif i > 0 and j > 0:dp[i][j] = dp[i-1][j] + dp[i][j-1]return dp[m-1][n-1]

LeetCode 63. 不同路径II

力扣题目链接
本题就是添加了障碍，只需保证dp数组在障碍的位置始终是0即可。

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

今日毕！