不同路径1
# 机器人从(0,0)出发，到达(m-1,n-1)终点 一共有几种路径
# 确定初始数组:dp二维数组 m行n列 表示到m行n列有几种路径
dp=[[0] * n for _ in range(m)]
dp[0][0]=1
for i in range(m):
dp[i][0]=1
for j in range(n):
dp[0][j]=1
# dp[1][1]=2
for i in range(1,m):
for j in range(1,n):
dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[m-1][n-1]
不同路径2
有障碍物版本
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m = len(obstacleGrid) # 网格的行数
n = len(obstacleGrid[0]) # 网格的列数
if m <= 1 and n <= 1 :
return 1 if obstacleGrid[0][0]==0 else 0
if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1:
# 如果起点或终点有障碍物，直接返回0
return 0
dp = [[0] * n for _ in range(m)] # 创建一个二维列表用于存储路径数
# 设置起点的路径数为1
dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
# 初始化第一行和第一列的状态
for i in range(1,m):
if obstacleGrid[i][0]==1:
continue
# 第一行或第一列的状态也是由前一个状态决定的
dp[i][0]=dp[i-1][0]
for i in range(1,n):
if obstacleGrid[0][i]==1:
continue
dp[0][i]=dp[0][i-1]
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]
