腾讯云

文章/答案/技术大牛

发布

社区首页 >专栏 >DP(动态规划)经典路径问题 | LeetCode

DP(动态规划)经典路径问题 | LeetCode

做棵大树

发布于 2022-09-27 11:57:46

56900

代码可运行

文章被收录于专栏：代码日志代码日志

运行总次数：0

代码可运行

一定要认真看完这篇文章✌ 大树不敢保证看完你就可掌握动态规划，但是，你一定可以 AC 动态规划中的路径问题！！😉 由于篇幅限制也为了不让大家产生阅读疲劳，980. 不同路径 III 这道题目会单独写一篇作为路径问题的收尾篇。

动态规划中的路径问题，题目来自于 LeetCode，子标题为 题号名称 的格式。

62 不同路径

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

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

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

img

例如，上图是一个7 x 3 的网格。有多少可能的路径？

示例 1:

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

向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右

示例 2:

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

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9

根据移动规则，我们可以确定，在 [i, j] 位置的点，只能通过 [i-1, j] 以及 [i, j-1] 到达

由以上分析，我们可以写出 solution 代码

Solution

class Solution {
    public int uniquePaths(int m, int n) {
        // 定义dp数组，数组中的值代表到达该位置的路径数目
        int[][] dp = new int[m][n];
        // 初始化第一行&第一列数值，因为只能向下和向右，所以值默认为1
        for(int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for(int j = 0; j < n; j++){
            dp[0][j] = 1;
        }
        // 根据移动规则，我们可以确定，在 [i, j] 位置的点，只能通过 [i-1, j] 以及 [i, j-1] 到达
        // 所以 dp[i][j]  = dp[i-1][j] + dp[i][j-1]
        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];
    }
}

对于该解决方案，其时间复杂度与空间复杂度为：

时间复杂度：O(m * n)
空间复杂度：O(m * n)

我们知道，通常对于DP题目的初始解法，是可以对其空间复杂度进行优化的，比如这道题目，我们刚开始用了二维数组来存储，所以消耗空间为 O(m * n) 但我们完全可以压缩为一维数组存储，下面我们就来尝试实现一下。

依然记得，规则：路径数 （i,j) = （i-1,j) + （i, j-1)

Solution·space-optimization

class Solution {
    public int uniquePaths(int m, int n) {
        int[] result = new int[m];
        // 初始化首行信息
        for(int i = 0; i < m; i++) result[i] = 1;
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                // 更新数组，当前位置 = 更新后的左侧 + 更新前的上一位
                result[j] += result[j-1];
            }
        }
        return result[m-1];
    }
}

63. 不同路径 II

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

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

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

img

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

说明： m 和 n 的值均不超过 100。

示例 1:

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

向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右

对于 不同路径 II 该题我们可以发现，相对于第一题，多了一个限制条件 考虑网格中有障碍物，那这个条件对于我们解决该题而言有什么含义呢？

这个点无法到达 -> 到达的路径为 0

所以我们对这个条件进行限定后就转变为同第一题相同的问题了。

Solution

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid == null){
            return 0;
        }

        int nr = obstacleGrid.length, nc = obstacleGrid[0].length;
        int[][] dp = new int[nr][nc];
        // 初始化边界条件
        for(int r = 0; r < nr; r++){
            // 若该边界为1，即障碍物，则之后的点均不可达，直接break
            if(obstacleGrid[r][0] == 1) break;
            dp[r][0] = 1;
        }
        for(int c = 0; c < nc; c++){
            if(obstacleGrid[0][c] == 1) break;
            dp[0][c] = 1;
        }
        // 循环填充内部数据
        for(int r = 1; r < nr; r++){
            for(int c = 1; c < nc; c++){
                if(obstacleGrid[r][c] == 1) {
                    // 障碍物，不可到达，所以直接填写为 0
                    dp[r][c] = 0; 
                    continue;
                }
                dp[r][c] = dp[r-1][c] + dp[r][c-1];
            }
        }
        return dp[nr-1][nc-1];
    }
}

✌ Kill 掉该题了

对于该解决方案，其时间复杂度与空间复杂度同第一题优化前的解法相同。

好，下边我们来进行一下优化，这个dp的优化呢，我们就不再去做将 O(m*n) 优化到 O(m) 的空间优化了。我们可以直接将其进行原地的dp，优化到 O(1）的时间复杂度。

注意了！ 😎

根据题目中传递的参数，我们可以发现，它本身就是一个二维数组，所以我们设想在它自身进行计数，从而省去空间上的消耗。

Solution·space-optimization

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid == null || obstacleGrid[0][0] == 1){
            // 若左上角为障碍物，直接返回0
            return 0;
        }

        int nr = obstacleGrid.length, nc = obstacleGrid[0].length;
        // 初始化边界条件
        for(int r = 0; r < nr; r++){
            if(obstacleGrid[r][0] == 1){
                for(int i = r; i < nr; i++){
                    // 如果发现一个1，则将后续全部置为0
                    obstacleGrid[i][0] = 0;
                }
                break;
            }
            obstacleGrid[r][0] = 1;
        }

        for(int c = 1; c < nc; c++){
            // 注意这里的 c 初始为 1， 大家可以考虑下为什么？
            if(obstacleGrid[0][c] == 1) {
                for(int j = c; j < nc; j++){
                    obstacleGrid[0][j] = 0;
                }
                break;
            }
            obstacleGrid[0][c] = 1;
        }
        // 循环填充内部数据
        for(int r = 1; r < nr; r++){
            for(int c = 1; c < nc; c++){
                if(obstacleGrid[r][c] == 1) {
                    obstacleGrid[r][c] = 0; 
                    continue;
                }
                obstacleGrid[r][c] = obstacleGrid[r-1][c] + obstacleGrid[r][c-1];
            }
        }
        return obstacleGrid[nr-1][nc-1];
    }
}