leetcode刷题笔记-62不同路径和63不同路径2

62 不同路径

题目

https://leetcode.cn/problems/unique-paths/

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

image.png

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) {
        // m 是行，n是列
        // dp方程是 dp[i][j] = dp[i-1][j] + dp[i][j-1]
        vector<vector<int>> v(m, vector<int>(n));
        // 因为只能向右和向下走，从0,0开始
        // 所以能直接推出来一部分结果，将第一行和第一列都初始化为1
        for (int i = 0; i < m; i++) {
            v[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            v[0][j] = 1;
        }
        // 其他部分是用dp计算
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 当前的路径数量是上一位往右（v[i][j-1]）和上一位往下（v[i - 1][j]）的和
                v[i][j] = v[i - 1][j] + v[i][j - 1];
            }
        }
        return v[m - 1][n - 1];
    }
};

image.png

代码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) {
        // 初始化为1，相当于将第一行设置为1
        vector<int> dp(n, 1);
        // 从第二行开始
        for (int i = 1; i < m; i++) {
            // 从第二列开始，相当于保留第一列始终为1
            for (int j = 1; j < n; j++) {
                // += 保留上一行的结果
                // 加上 dp[j-1] 等于左边的结果
                dp[j] += dp[j - 1];
            }
        }
        // 返回左下角的结果
        return dp[n - 1];
    }
};

image.png

63 不同路径2

题目

https://leetcode.cn/problems/unique-paths-ii/description/

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

image.png

思路

这道题在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();
        // m 是行，n是列
        // dp方程是 dp[i][j] = dp[i-1][j] + dp[i][j-1]
        vector<vector<int>> v(m, vector<int>(n));
        // 因为只能向右和向下走，从0,0开始
        // 所以能直接推出来一部分结果，将第一行和第一列都初始化为1
        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;
            }
        }
        // 其他部分是用dp计算
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 当前的路径数量是上一位往右（v[i][j-1]）和上一位往下（v[i-1][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; // 不能走的初始化为0
                }
                if (up < 0) {
                    up = 0;
                }
                v[i][j] = up + left;
            }
        }
        // 因为我是用-1来设置到不了的，最终就需要修正为0
        return v[m - 1][n - 1] == -1 ? 0 : v[m - 1][n - 1];
    }
};

image.png

代码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) {
        // m 是行，n是列
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> v(m, vector<int>(n));
        // 因为只能向右和向下走，从0,0开始
        // 所以能直接推出来一部分结果，将第一行和第一列都初始化为1
        bool isBlock = false; // 是否有阻碍？
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1 || isBlock) {
                v[i][0] = 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; // 不能走的初始化为0
                isBlock = true; // 注意，只要有一个阻碍，就不能往下走了
            } else {
                v[0][j] = 1;
            }
        }
        // 其他部分是用dp计算
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 当前的路径数量是上一位往右（v[i][j-1]）和上一位往下（v[i-1][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