动态规划DP--unique path --从左上角到右下角走法的种数
程序员文章站
2022-03-05 18:28:37
...
题目描述
一个机器人在m×n大小的地图的左上角(起点,下图中的标记“start"的位置)。
机器人每次向下或向右移动。机器人要到达地图的右下角。(终点,下图中的标记“Finish"的位置)。
可以有多少种不同的路径从起点走到终点?
循环----
class Solution:
def uniquePaths(self , m , n ):
# write code here
res=[[0 for i in range(n)] for j in range(m)]
for i in range(n):
res[0][i]=1
for j in range(m):
res[j][0]=1
for i in range(1,m):
for j in range(1,n):
res[i][j]=res[i-1][j]+res[i][j-1]
return res[m-1][n-1]
递归
class Solution:
def uniquePaths(self , m , n ):
# write code here
res=[[0 for i in range(n)] for j in range(m)]
if m==1 or n==1:
return 1
else:
return self.uniquePaths(m-1,n)+self.uniquePaths(m,n-1)