leetcode刷题笔记-62不同路径和63不同路径2
62 不同路径
题目
https://leetcode.cn/problems/unique-paths/
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
![image.png](/img/loading.gif)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| 示例 2: 输入:m = 3, n = 2 输出:3 解释: 从左上角开始,总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
示例 3: 输入:m = 7, n = 3 输出:28
示例 4: 输入:m = 3, n = 3 输出:6
|
思路
这道题需要用动态规划的方式来写。首先是确定递归数组每一位代表什么。根据题意可以想出来dp[i][j]
代表走到(i,j)
位置的可行步骤数量。
随后是考虑递归方程,因为机器人只能向右和向下走,很容易得到下面的方程。即能到达当前位置的方法是走到左边那位(下一步往右走)和上面那位(下一步向下走)的步骤数之和。
1
| dp[i][j] = dp[i-1][j] + dp[i][j-1]
|
再考虑怎么设置这个数组的初始值。因为机器人只能向下和向右走,即这个数组的第一行和第一列都只有一种办法可以抵达,即将第一行和第一列中的值都初始化为1。
再从(1,1)
下标位置开始,使用公式计算出所有的值,并最终返回dp[m-1][n-1]
作为答案。
代码1:二维数组
代码如下
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 uniquePaths(int m, int n) { vector<vector<int>> v(m, vector<int>(n)); for (int i = 0; i < m; i++) { v[i][0] = 1; } for (int j = 0; j < n; j++) { v[0][j] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { v[i][j] = v[i - 1][j] + v[i][j - 1]; } } return v[m - 1][n - 1]; } };
|
![image.png](/img/loading.gif)
代码2:一维数组
上述代码中的时间复杂度不好优化,但是空间复杂度是可以优化的。我们可以将这个二维数组改成一个n长度(每一行)的一维数组。
首先是将这个数组初始化为1(因为第一行只有1种方式可以到达)。
然后同样是从下标(1,1)
位置开始遍历,此时的方程是dp[i] += dp[i-1]
。
用这种方式,巧妙的将二维的操作改成了一维的。加等操作相当于保留了上一行的结果,加上dp[i-1]
相当于保留了左边那位(下一步向右走)的结果。这个思路很巧妙,建议画个矩阵来自行理解一下。
最终的代码如下。
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) { vector<int> dp(n, 1); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] += dp[j - 1]; } } return dp[n - 1]; } };
|
![image.png](/img/loading.gif)
63 不同路径2
题目
https://leetcode.cn/problems/unique-paths-ii/description/
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
![image.png](/img/loading.gif)
思路
这道题在62题的基础上多加了一个障碍物,遇到障碍物肯定就无法抵达了,需要我们针对障碍物进行处理。
先采用上一题的二维数组的思路,考虑遇到障碍物应该怎么处理。这里我想的办法是用-1
来标识障碍物,即当前位置无法到达。
- 第一行和第一列有障碍物,往后的位置都无法抵达,往后的位置都要初始化为
-1
; - 判断
obstacleGrid[i][j]
是否有障碍物,有则dp[i][j]
为-1
,无法抵达; dp[i][j]
需要判断dp[i-1][j]
和 dp[i][j-1]
这两个位置是否有障碍物- 如果两个位置都是负一,则代表
dp[i][j]
无法到达,初始化为-1
; - 只有一个位置是负一,则代表当前位置可以到达,值为不为负一的那一个;
- 两个位置都不为负一,则是正常的情况,值为
dp[i-1][j] + dp[i][j-1]
。
把这些情况都考虑上,只需要在原本的代码上修改一下就可以了
代码1
特别要注意的是第一行和第一列的情况,因为他们都只有一条可行的路径,那只要遇到了一个阻碍,后面的位置就都到不了了!都需要赋值为0!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(), n = obstacleGrid[0].size(); vector<vector<int>> v(m, vector<int>(n)); bool isBlock = false; for (int i = 0; i < m; i++) { if (obstacleGrid[i][0] == 1 || isBlock) { v[i][0] = -1; isBlock = true; } else { v[i][0] = 1; } } isBlock = false; for (int j = 0; j < n; j++) { if (obstacleGrid[0][j] == 1 || isBlock) { v[0][j] = -1; isBlock = true; } else { v[0][j] = 1; } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { int left = v[i][j - 1]; int up = v[i - 1][j]; if (obstacleGrid[i][j] == 1 || (left < 0 && up < 0)) { v[i][j] = -1; continue; } if (left < 0) { left = 0; } if (up < 0) { up = 0; } v[i][j] = up + left; } } return v[m - 1][n - 1] == -1 ? 0 : v[m - 1][n - 1]; } };
|
![image.png](/img/loading.gif)
代码2
实际上完全不需要用负一来标识到不了,每一次还需要判断将其修正为0。我们直接用0代表到不了就行了,可以节省几个判断,代码看起来也会舒服一点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(), n = obstacleGrid[0].size(); vector<vector<int>> v(m, vector<int>(n)); bool isBlock = false; for (int i = 0; i < m; i++) { if (obstacleGrid[i][0] == 1 || isBlock) { v[i][0] = 0; isBlock = true; } else { v[i][0] = 1; } } isBlock = false; for (int j = 0; j < n; j++) { if (obstacleGrid[0][j] == 1 || isBlock) { v[0][j] = 0; isBlock = true; } else { v[0][j] = 1; } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { int left = v[i][j - 1]; int up = v[i - 1][j]; if (obstacleGrid[i][j] == 1 || (left <= 0 && up <= 0)) { v[i][j] = 0; continue; } v[i][j] = up + left; } } return v[m - 1][n - 1]; } };
|
![image.png](/img/loading.gif)