本文主要是介绍【代码随想录】【动态规划】day39:不同路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
不同路径1
# 机器人从(0,0)出发，到达(m-1,n-1)终点 一共有几种路径# 确定初始数组:dp二维数组 m行n列 表示到m行n列有几种路径dp=[[0] * n for _ in range(m)]dp[0][0]=1for i in range(m):dp[i][0]=1for j in range(n):dp[0][j]=1# dp[1][1]=2for 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 0if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1:# 如果起点或终点有障碍物，直接返回0return 0dp = [[0] * n for _ in range(m)] # 创建一个二维列表用于存储路径数# 设置起点的路径数为1dp[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:continuedp[0][i]=dp[0][i-1]for i in range(1,m):for j in range(1,n):if obstacleGrid[i][j]==1:continuedp[i][j]=dp[i-1][j]+dp[i][j-1]return dp[m-1][n-1]
这篇关于【代码随想录】【动态规划】day39:不同路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
