题目-不同路径I
一个机器人位于一个m x n
网格的左上角 (起始点在下图中标记为Start
)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为Finish
)。
问总共有多少条不同的路径?
示例1
- 输入:m = 3, n = 7
- 输出:28
示例2
- 输入:m = 2, n = 3
- 输出:3
- 解释: 从左上角开始,总共有 3 条路径可以到达右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例3
- 输入:m = 7, n = 3
- 输出:28
示例4
- 输入:m = 3, n = 3
- 输出:6
思路-I
首先机械人要到达终点必须要向下走n
步,向右走m
步,我们将机械人的初始位置表示为(0 , 0)
,终点表示为(m-1 , n-1)
。
动态规划五步曲-I
-
确定
dp
数组以及下标的含义
dp[i][j]
:表示从(0 ,0)
出发,到(i, j)
有dp[i][j]
条不同的路径。 -
确定递推公式
想要求dp[i][j]
,只能有两个方向来推导出来,即从[i][j]
位置的上方和左方移动而来,代码表示为dp[i - 1][j]
和dp[i][j - 1]
。
此时在回顾一下dp[i - 1][j]
表示啥,是从(0, 0)
的位置到(i - 1, j)
有几条路径,dp[i][j - 1]
同理。
那么很自然,dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
,因为dp[i][j]
只有这两个方向过来。
-
dp数组的初始化
如何初始化呢,首先dp[i][0]
一定都是1
,因为从(0, 0)
的位置到(i, 0)
的路径只有一条,那么dp[0][j]
也同理。 -
确定遍历顺序
这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
,dp[i][j]
都是从其上方和左方推导而来,那么从左到右一层一层遍历就可以了。 -
举例推导
dp
数组
代码实现-I
1 | class Solution { |
题目-不同路径II
一个机器人位于一个m x n
网格的左上角 (起始点在下图中标记为Start
)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为Finish
)。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
注:网格中的障碍物和空位置分别用
1
和0
来表示。
示例1
- 输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
- 输出:2
- 解释:3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径:
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
示例2
- 输入:obstacleGrid = [[0,1],[0,0]]
- 输出:1
思路-II
首先这个题跟不同路径I很相似,则我们定义dp[i][j]
为到达(i,j)
的路径数,已知有障碍就无法通行,且dp
数组会遍历到网格上的每一个点,则我们只需要令以障碍点为终点的路径删去就是没有障碍的路径,在这个思路中我们直接排除了含障碍点的路径。
动态规划五部曲-II
-
确定
dp
数组以及下标的含义
dp[i][j]
:表示从(0 ,0)
出发,到(i, j)
有dp[i][j]
条不同的路径。 -
确定递推公式
递推公式和62.不同路径一样,dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
。
注:但这里需要注意一点,因为有了障碍,
(i, j)
如果就是障碍的话应该就保持初始状态(初始状态为0)。
dp
数组如何初始化
在(i,0)
不是障碍物之前,其路径数都是1
,当(i,0)
位置为障碍物之后,其路径数都为0
.
1 | for(int i = 0; i < m && obstacleGrid[i][0] != 1; i++){ |
注:注意代码里for循环的终止条件,一旦遇obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作,dp[0][j]同理
-
确定遍历顺序
从递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
中可以看出,一定是从左到右一层一层遍历,这样保证推导dp[i][j]
的时候dp[i - 1][j]
和dp[i][j - 1]
一定是有数值。 -
举例推导
dp
数组
自己想象
1 | class Solution { |