本题大家掌握动态规划的方法就可以。?数论方法?有点非主流，很难想到。?
视频讲解：动态规划中如何初始化很重要！| LeetCode：62.不同路径_哔哩哔哩_bilibili
class Solution(object):
def uniquePaths(self, m, n):
if m==1 and n==1:
return 1
dp=[[0]*n]*m
dp[0][0]=1
for x in range(m):
for y in range(n):
if x>0 and y>0:
dp[x][y]=dp[x-1][y]+dp[x][y-1]
if x==0 or y==0:
dp[x][y]=1
return dp[m-1][n-1]把m和n弄反了。
视频讲解：动态规划，这次遇到障碍了| LeetCode：63. 不同路径 II_哔哩哔哩_bilibili
我本来想的是用高中的遇到障碍的题来解的，结果他没说有几个障碍，这个方法只能解决一个障碍的，就是减去经过这个障碍的路径。
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
m=0
n=0
x=len(obstacleGrid)
y=len(obstacleGrid[0])
if x==1 and y==1:
if obstacleGrid[0][0]==1:
return 0
return 1
for i in range(x):
for j in range(y):
if obstacleGrid[i][j]==1: #表示遇到障碍
if i==x-1 and j==y-1:
return 0
m=i
n=j #表示障碍的坐标
if i>0 and j>0:
obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1]
elif (i==0 or j==0) and (i>0 or j>0):
obstacleGrid[i][j]=1
pre=obstacleGrid[m][n]*obstacleGrid[x-m-1][y-n-1]
return obstacleGrid[x-1][y-1]-preclass Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
m = len(obstacleGrid)
n = len(obstacleGrid[0])
if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1:
return 0
dp = [[0] * n for _ in range(m)]
for i in range(m):
if obstacleGrid[i][0] == 0: # 遇到障碍物时，直接退出循环，后面默认都是0
dp[i][0] = 1
else:
break
for j in range(n):
if obstacleGrid[0][j] == 0:
dp[0][j] = 1
else:
break
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
continue
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
我应该从他的定义出发的，dp[i][j]的定义就是从开始坐标到当前坐标的路径的数量，所以我直接为0就表是有障碍了呀。