阿里云网站备案拍照点,做网页需要什么,软件开发工程师需要具备的能力,网站开发设计概述题目#xff1a;62. 不同路径
难度#xff1a;中等
一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;在下图中标记为 “Finish” #x…题目62. 不同路径
难度中等
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径
示例 1 输入m 3, n 7
输出28
示例 2
输入m 3, n 2
输出3
解释
从左上角开始总共有 3 条路径可以到达右下角。
1. 向右 - 向下 - 向下
2. 向下 - 向下 - 向右
3. 向下 - 向右 - 向下示例 3
输入m 7, n 3
输出28示例 4
输入m 3, n 3
输出6提示
1 m, n 100题目数据保证答案小于等于 2 * 109
一、模式识别
本题我一共找到了三种解法
首先最容易想到的就是基于递归的DFS深度优先搜索
然后如果沿着递推公式能想到从终点返回起点这一层就能写出动态规划解法
最后代码随想录还给出了算组合数的方法数论我数学没那么好想不到
1.DFS
该方法顺着题干很容易想到而且该方法就是动态规划方法的递推公式
2.动态规划
本题属于经典动态规划问题而且动规的很多要素题干中已经直接给出
五部曲
1.动规数组意义位于位置(i, j)时剩余的总步数
2.递推公式dp(i, j) dp(i - 1, j) dp(i, j - 1)
解释
机器人处于位置(i, j)时每次只能向下或者向右移动一步两种选择
分别可以到达(i - 1, j)和位置(i, j - 1)
3.初始化题干一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start”
4.遍历顺序本题常规根据递推公式
行遍历套列遍历或列遍历套行遍历均可但注意是从终点反向到起点
5.举例当机器人走到边缘位置(m 1 or n 1)路径便只剩下一条
3.数论算组合数
无论怎么走从起点(m, n)到终点(1, 1)都要走m n - 2步
其中横向m - 1步纵向n - 1步
因此该问题就顺理成章的转化成了C(m n - 2), (m - 1)的组合问题
二、代码实现
1.DFS
这方法很好想而且代码简介可读性强但就是有个小小的问题会超时
class Solution:def uniquePaths(self, m: int, n: int) - int:if m 1 or n 1:return 1return self.uniquePaths(m - 1, n) self.uniquePaths(m, n - 1)
问题源于其指数级的时间复杂度O(2^(m n - 1) - 1)
2.动态规划
1二维OMN空间写法
class Solution:def uniquePaths(self, m: int, n: int) - int:if m 1 or n 1:return 1dp [[1] * n for _ in range(m)]for i in range(m):for j in range(n):if i ! 0 and j ! 0:dp[i][j] dp[i - 1][j] dp[i][j - 1]return dp[m - 1][n - 1]
时间复杂度O(m × n)空间复杂度O(m × n)
耗时0ms
2一维ON空间写法
class Solution:def uniquePaths(self, m: int, n: int) - int:if m 1 or n 1:return 1dp [1] * nfor i in range(m):for j in range(n):if i ! 0 and j ! 0:dp[j] dp[j - 1]return dp[n - 1]
时间复杂度O(m × n)空间复杂度O(n)
耗时3ms
可读性有点差所以稍微解释一下和二维空间代码的对应关系
dp[i][j] dp[i - 1][j] dp[i][j - 1] 和 dp[j] dp[j - 1]
dp[i][j]: 更新后的dp[j]
dp[i - 1][j]: 更新前的dp[j]
dp[i][j - 1]: dp[j - 1]
3.数论算组合数
class Solution:def uniquePaths(self, m: int, n: int) - int:num 1a, b m n - 2, min(m - 1, n - 1)count bwhile count 0:num * aa - 1while b 0 and num % b 0:num // bb - 1count - 1return num
时间复杂度O(m)空间复杂度O(1)
耗时0ms
