力扣 63 不同路径②【动规五步法】【dp数组初始化】

力扣 63 不同路径二② 【动规五步法】

文章目录

• 力扣 63 不同路径二② 【动规五步法】
• • 全部刷题与学习记录
  • 原题目
  • 考查知识点
  • 自己的第一遍解法
  • 好的解法

全部刷题与学习记录

【C++刷题学习笔记目录】

【C++百万并发网络通信-笔记目录】

原题目

题目地址：63. 不同路径 II

考查知识点

dp数组究竟代表什么意思、dp数组的初始化

自己的第一遍解法

刚开始按照五步法来，结果体会到了弄清楚dp数组意义的重要性，题目要求：

那么从左上角到右下角将会有多少条不同的路径？

我在这里把

dp[i] [j]

定义成了从

（i，j）

到右下角有多少路径，这跟正确的dp数组意义截然相反。一个没有障碍的地图，随着

i，j

的增加，前往右下角的路径只会越来越多，但是在我这种定义方式下，

dp[i] [j]

只会越来越少。正确的dp数组意义应该是：

dp[i] [j]

代表从

(0, 0)

到

(i, j)

有多少路径。

在改正dp数组的意义后，下面的代码中因为初始化没做好（因为存在障碍），导致代码鲁棒性不高，需要单独用if语句处理很多情况（比如地图是

1×1

，

n×1

，

1×n

并且以上情况均需要考虑是否有障碍存在），这样是十分不好的

好的解法

【代码随想录】大佬给出了正确的思路，首先就是正确的dp数组意义；其次，是dp数组的初始化思路。不同于力扣 62 不同路径【动态规划五步法】中直接对两条边不加区分的赋1，现在出现的问题是如果边上一旦出现障碍，障碍当前的位置以及之后的位置在dp数组的对应处都应该是0

那么在两层for循环，从上到下，从左到右的遍历中，如果当前位置出现障碍，在dp数组的当前位置也要保持0

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};
           

参考：

https://mp.weixin.qq.com/s/lhqF0O4le9-wvalptOVOww