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）,但深搜时间复杂度会比较高，我这里就用动态规划解决这个问题
• 因为只能向下和向右，所以我们这里起始状态就是第0行和第0列都是1，就是只有一种走法可以这样。（状态初始化）接下来，从第1行第1列开始遍历，dp[i][j] = dp[i-1][j] + dp[i][j-1](递推公式，即当前格子的可能路径数等于上面格子和左边格子的可能路径和，因为左边格子走一步和上边格子走一步可以到当前格子)
• 如果只有一行或者一列，就证明只有一条路，这里单独列出，当然也可以不列，对结果没有影响。

代码（动态规划）

class Solution:def uniquePaths(self, m: int, n: int) -> int:if m == 1 or n == 1:return 1dp = [[1] * n] * m # 创建m行n列的数组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[m-1][n-1]

通过截图

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1提示：m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

分析

• 和上面那题很像，但难度增加，因为有了障碍。但没有影响。
• 对于障碍的处理，我们只需要分，我们这个格子是障碍，和我们这个格子不是障碍。
• 是障碍，那么我不做处理，因为没有什么值得处理，本身这格也不能走。
• 不是障碍，那么我和前面一样用上面格子和左边格子的可能路径数，有人可能会说：如果上面或者左边格子存在障碍呢？没关系，障碍为0不就没有影响了吗？
• 这里有个坑：就是不要直接用[[0]*n]*m去创建m行n列的数组。通过对地址的查询，发现这样创建出来的每行地址相同。一行进行修改，其他行会一起修改。用这种方法创建即可[[0]*n for _ in range(m)]
• 初始化时，如果碰到障碍那就不要管了，前面的格为1即可。

代码（动态规划）

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:m = len(obstacleGrid) # 行n = len(obstacleGrid[0]) # 列    dp = [[0]*n for _ in range(m)] # 创建m行n列的0for i in range(m): # 第0列初始化为1if not obstacleGrid[i][0]:dp[i][0] = 1else:breakfor j in range(n): # 第0行初始化为1if not obstacleGrid[0][j]:dp[0][j] = 1else:breakfor i in range(1,m):for j in range(1,n):if not obstacleGrid[i][j]: # 这里不是障碍物dp[i][j] = dp[i-1][j] + dp[i][j-1] # 上加左return dp[m-1][n-1]

通过截图

如有错误，敬请指正，欢迎交流，谢谢♪(･ω･)ﾉ