少女祈祷中...

题目-不同路径I

一个机器人位于一个m x n网格的左上角 (起始点在下图中标记为Start)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为Finish)。
问总共有多少条不同的路径?
62-1

示例1

  • 输入:m = 3, n = 7
  • 输出:28

示例2

  • 输入:m = 2, n = 3
  • 输出:3
  • 解释: 从左上角开始,总共有 3 条路径可以到达右下角。
    1. 向右 -> 向右 -> 向下
    2. 向右 -> 向下 -> 向右
    3. 向下 -> 向右 -> 向右

示例3

  • 输入:m = 7, n = 3
  • 输出:28

示例4

  • 输入:m = 3, n = 3
  • 输出:6

《代码随想录》算法公开课
力扣题目链接

思路-I

首先机械人要到达终点必须要向下走n步,向右走m步,我们将机械人的初始位置表示为(0 , 0),终点表示为(m-1 , n-1)

动态规划五步曲-I

  1. 确定dp数组以及下标的含义
    dp[i][j] :表示从(0 ,0)出发,到(i, j)dp[i][j]条不同的路径。

  2. 确定递推公式
    想要求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]只有这两个方向过来。

  1. dp数组的初始化
    如何初始化呢,首先dp[i][0]一定都是1,因为从(0, 0)的位置到(i, 0)的路径只有一条,那么dp[0][j]也同理。

  2. 确定遍历顺序
    这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]dp[i][j]都是从其上方和左方推导而来,那么从左到右一层一层遍历就可以了。

  3. 举例推导dp数组
    62-2

代码实现-I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int uniquePaths(int m, int n) {
//行列的索引都从0出发,则终点位置索引为[m-1][n-1]
int[][] dp = new int[m][n];
//初始化
for(int i = 0; i < m; i++)dp[i][0] = 1;
for(int i = 0; i < n; i++)dp[0][i] = 1;

//因为每次只能向下或向右移动一步,则dp[i][j] 只能来自dp[i][j-1]向右移动一步,或者dp[i-1][j]向下移动一步
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}

return dp[m-1][n-1];
}
}

题目-不同路径II

一个机器人位于一个m x n网格的左上角 (起始点在下图中标记为Start)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为Finish)。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

注:网格中的障碍物和空位置分别用10来表示。

示例1

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

示例2

  • 输入:obstacleGrid = [[0,1],[0,0]]
  • 输出:1

《代码随想录》算法公开课
力扣题目链接

思路-II

首先这个题跟不同路径I很相似,则我们定义dp[i][j]为到达(i,j)的路径数,已知有障碍就无法通行,且dp数组会遍历到网格上的每一个点,则我们只需要令以障碍点为终点的路径删去就是没有障碍的路径,在这个思路中我们直接排除了含障碍点的路径。

动态规划五部曲-II

  1. 确定dp数组以及下标的含义
    dp[i][j]:表示从(0 ,0)出发,到(i, j)dp[i][j]条不同的路径。

  2. 确定递推公式
    递推公式和62.不同路径一样,dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

注:但这里需要注意一点,因为有了障碍,(i, j)如果就是障碍的话应该就保持初始状态(初始状态为0)。

  1. dp数组如何初始化
    (i,0)不是障碍物之前,其路径数都是1,当(i,0)位置为障碍物之后,其路径数都为0.
1
2
3
4
5
6
for(int i = 0; i < m && obstacleGrid[i][0] != 1; i++){
dp[i][0] = 1;
}
for(int j = 0; j < n && obstacleGrid[0][j] != 1; j++){
dp[0][j] = 1;
}

注:注意代码里for循环的终止条件,一旦遇obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作,dp[0][j]同理

  1. 确定遍历顺序
    从递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 中可以看出,一定是从左到右一层一层遍历,这样保证推导dp[i][j]的时候dp[i - 1][j]dp[i][j - 1]一定是有数值。

  2. 举例推导dp数组
    自己想象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;

int[][] dp = new int[m][n];
if(obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1)return 0;
//遇到障碍物后面都是0,数组的初始值都是0
for(int i = 0; i < m && obstacleGrid[i][0] != 1; i++){
dp[i][0] = 1;
}
for(int j = 0; j < n && obstacleGrid[0][j] != 1; j++){
dp[0][j] = 1;
}

//dp数组会普及到每一个位置,只要当前是障碍物就直接不通,默认初始值为0
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[i][j] = (obstacleGrid[i][j] == 0)? dp[i-1][j] + dp[i][j-1] : 0;
}
}
return dp[m-1][n-1];
}
}