vlambda博客
学习文章列表

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

一定要认真看完这篇文章✌

大树不敢保证看完你就可掌握动态规划,但是,你一定可以 AC 动态规划中的路径问题!!😉

由于篇幅限制也为了不让大家产生阅读疲劳,980. 不同路径 III 这道题目会单独写一篇作为路径问题的收尾篇。

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

62 不同路径

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

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

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

img

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

示例 1:

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

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  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

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

说明: mn 的值均不超过 100。

示例 1:

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

  1. 向右 -> 向右 -> 向下 -> 向下
  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] == 1break;
            dp[r][0] = 1;
        }
        for(int c = 0; c < nc; c++){
            if(obstacleGrid[0][c] == 1break;
            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];
    }
}

可以看到,在上边代码中,初始化首列时的初始条件为 int c = 1; c < nc; c++,为什么是从1开始呢?

其实是因为我们在初始化行的时候,将 obstacleGrid[0][0] 的位置置为了 1,所以如果我们在初始列时依旧从0开始就会将左上角的 1 看作为障碍物,从而无法到达。

但是因为在函数开始时,我们便进行了判断 if(obstacleGrid == null || obstacleGrid[0][0] == 1),所以左上角的 1 必然是我们修改后的,而非障碍物。

image-20200901224120987

经过这次优化,最终空间复杂度只有常量级别;在做题时候可以用,但是如果要用在实际环境中不建议直接对原数组进行修改哦~ 😉


如果你看到了这,恭喜你又读完了一篇文章!

至此本文已经逼近2000字了,为了保证不产生阅读疲倦,路径问题的最后一个 boss  980. 不同路径 III 这道题目会单独写一篇作为DP路径问题的完结篇。


点个在看吧 👇👇