一家装修的网站怎么做,温州网站建设公司哪个好,物联网平台开源,shortcode wordpress1 问题
一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;在下图中标记为 “Finish” #xff09;。
问总共有多少条不同的路径#xff1f…1 问题
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径
示例 1 输入m 3, n 7 输出28
示例 2
输入m 3, n 2 输出3 解释 从左上角开始总共有 3 条路径可以到达右下角。
向右 - 向下 - 向下向下 - 向下 - 向右向下 - 向右 - 向下
2 答案
这题直接不会
官方解
排列组合机器到底右下角向下几步向右几步都是固定的。
class Solution:def uniquePaths(self, m: int, n: int) - int:return int(math.factorial(mn-2)/math.factorial(m-1)/math.factorial(n-1)) # math.factorial(mn-2) 为 mn-2 的阶乘动态规划 令 dp[i][j] 是到达 i, j 最多路径 则动态规划转移方程dp[i][j] dp[i-1][j] dp[i][j-1]左边一格的最多路径上面一格的最多路径
class Solution:def uniquePaths(self, m: int, n: int) - int:dp [[1]*n] [[1][0] * (n-1) for _ in range(m-1)]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[-1][-1]优化动态规划转移方程dp[i]dp[i-1]
class Solution:def uniquePaths(self, m: int, n: int) - int:cur [1] * n # 代表第一行for i in range(1, m):for j in range(1, n):cur[j] cur[j-1] # 代表这个位置上一行的数据又上一行到这行只有一种路径因此只需要再加上左侧右移的路径便可以return cur[-1]
