文章目录
- 62.不同路径:
- 题目描述
- 简化题目
- 思路分析
- 完整代码
- 63.不同路径 II
62.不同路径:
题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
简化题目
每次可以往右或者往下走一格，从左上走到右下一共有多少种路径。
思路分析
动规五步走：
1.确定dp数组含义：
dp[i][j] 表示 从左上角出发点到[i][j]格有多少种路径。
2.确定递推公式：
动态规划问题都有一种局部操作的思想，这道题就是看到[i][j]有几种路径由谁决定，由于题目已经说了，只能由往右边或者下边走，所以到[i][j] 的不同路径数，由dp[i-1][j]和dp[i][j-1]相加决定。
所以有递推公式：dp[i][j] = dp[i-1][j]+dp[i][j-1]
3.初始化dp数组：
由于只能往右或者往下走，所以他们的值都是1，也就是只有一种路径方法。
dp[0][i] 和dp[j][0]都是1.
4.确定遍历顺序：
从左到右一层一层遍历就行了。
5.模拟dp结果：
直接偷一张图。最终结果显然是dp[-1][-1]。
完整代码
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp =[[1 for i in range(n)]for j in range(m)]
for i in range(1,m):
for j in range(1,n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp)
return dp[-1][-1] 63.不同路径 II
这道题根据上一道题改了一下，他在棋盘上加了障碍物。
还是从左上角到右下角，问你有几种路径方法，中间加了一块红色的障碍物。
与上一题不同的地方就是初始化有较大不同，其他位置基本没变。
可以想象一种情况，就是这个障碍物在最左边或者在最上边的情况。
比如
那么在dp数组里就是 1，1，1，1，0，0，0。
在上一题已经说过了，最左边和最上边所有的点都是只有一种走法，因为只能走右边或者下边。所以如果障碍物在最左边或者最上边的话，那么最左一条边或最上一条边的障碍物后面就都是0了，因为唯一的路径被切断了，没办法到达了。
一开始dp数组全部为0，只要障碍物不在起点，则就让dp[0][0] =1 依此来初始化dp[i][0]和dp[0][j]的值
这是和上一题初始化dp数组部分不太一样的地方。
另一个不一样的点就是在递推公式哪里，如果碰到障碍物，则不更新dp里的值，让dp数组对应障碍物的位置始终保持0，这样障碍物哪里的路径就一直是0了。
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
col = len(obstacleGrid[0])
row = len(obstacleGrid)
dp = [[0 for i in range(col)] for j in range(row)]
if obstacleGrid[0][0] == 1:
return 0
else:
dp[0][0] =1
for j in range(1,col):
if obstacleGrid[0][j]!=1:
dp[0][j] = dp[0][j-1]
for i in range(1,row):
if obstacleGrid[i][0]!=1:
dp[i][0] = dp[i-1][0]
for i in range(1,row):
for j in range(1,col):
if obstacleGrid[i][j] !=1:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]