那个网站建设好,下载中心,网络营销策划案框架,wordpress 评论美化1 问题
一个机器人位于一个 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]
