算法第39天动态规划2

news/2025/2/15 16:06:08/

62 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

在这里插入图片描述

# 递归
def uniquePaths(m:int,n:int)->int:if m==1 or n==1:return 1return uniquePaths(m-1,n)+uniquePaths(m,n-1)# 动态规划
def uniquePaths(m,n):dp=[[0]*n for _ in range(m)]: #dp[i][j]表示（0，0）到（i，j）有多少种方式到达for i in range(m):dp[i][0]=1for j in range(n):dp[0][j]=1for 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]# 数论
def uniquePaths(m,n):numerator=1denominator=m-1count=m-1 #走到(m-1,n-1)横着走，一定要走m-1步t=m+n-2 #走到(m-1,n-1)一共需要m+n-2步while count>0:numerator*=tt-=1while denominator!=0 and numerator%denominator==0: #不能分子全部乘完/分母全部乘完  防止存储溢出numerator//==denominatordenominator-=1count-=1return numerator

63 不同路径II

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

def uniquePathsWithObstacles(obstacleGrid:'List[List[int]]')->int:m=len(obstacleGrid)n=len(obstacleGrid[0])if obstacleGrid[m-1][n-1]==1 or obstacleGrid[0][0]==1:return 0dp=[[0]*n for _ in range(m)]for i in range(m):if obstacleGrid[i][0]==0:dp[i][0]=1else:breakfor j in range(n):if obstacleGrid[0][j]==0:dp[0][j]==1else:breakfor 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]def uniquePathsWithObstacles(obstacleGrid):if obstacleGrid[m-1][n-1]==1 or obstacleGrid[0][0]==1:return 0m=len(obstacleGrid)n=len(obstacleGrid[0])dp=[0]*n#存储路径数for j in range(n):if obstacleGrid[0][j]==1breakdp[j]=1for i in range(1,m):if obstacleGrid[i][0]==1:dp[0]=0for j in range(1,n):if obstacleGrid[i][j]==1:dp[j]=0else:dp[j]+=dp[j-1]return dp[-1]