代码随想录第39天 | 62.不同路径、 63. 不同路径 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了代码随想录第39天 | 62.不同路径、 63. 不同路径 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、前言

参考文献：代码随想录

今天主要的题目是动态规划的路径问题，动态规划五要点；

1、确定dp数组，dp[i]代表什么i代表什么；

2、递推公式；

3、初始化dp数组；

4、遍历顺序；

5、打印dp数组；

二、不同路径

1、思路：

我感觉动态规划，我听的很认真，然后这个题目，我有一点感觉，但是我又想不出来，只好去求看一下卡哥，但是才看了三分钟，我就想到思路了。。。

（1）dp数组，由于这是一个二维图，所以需要创建一个二维的dp数组，i,j分别代表一个点位，dp[i][j]代表到达该点的位置；

（2）初始化：我们发现，机器人只允许向右或者向下移动，所以在[i][0]上面的情况全是1，以及[0][j]也全是1，所以这就是初始化；

（3）递推公式：

当我把图画出来后不难发现当需要拐弯时，那个结点的情况就是上面的路径加上左边的路径；代码随想录第39天 | 62.不同路径、 63. 不同路径 II,leetcode,算法

（图很潦草）但是也能看懂，所以递推公式就是：

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

（4）遍历顺序：很显然，我们是要慢慢的积累我们不同路径的数量，所以是从最小的地方开始，但是不是用上边界和左边界，而是从[1][1]的地方开始；

2、整体代码如下：

class Solution {
public:
    int uniquePaths(int m, int n) {
        // 1、定义dp数组，i，j表示位置，dp[i][j]表示到达结点的次序
        vector<vector<int>> dp(m, vector<int>(n));
        // 2、初始化dp数组
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        // 3、遍历
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 4、递推公式
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        // 5、打印dp数组
        // for (int i = 0; i < m; i++) {
        //     for (int j = 0; j < n; j++) {
        //         cout << dp[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        return dp[m - 1][n - 1];
    }
};

三、不同路径||

1、思路：

这个题目和上一个不同路径的题目思路差不多，但是其中多了障碍物，所以在递推公式上，我们就得分很多种情况，来做出不同的措施；

（1）dp数组，与上一个题目的作用相同；

（2）初始化，这里的初始化就有一些区别。因为在初始化上边界和左边界时可能会出现障碍物，一旦出现，就需要把后面的路径数设置为0：

        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                for (int j = i; j < m; j++) {
                    dp[i][0] = 0;
                }
                break;
            }
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                for (int i = j; i < n; i++) {
                    dp[0][j] = 0;
                }
                break;
            }
            dp[0][j] = 1;
        }

（3）递推公式：在递推公式中，我们需要做出以下几种情况的判断，

1、如果当前[i][j]位置有障碍物，则直接设置为0；

2、如果上方有障碍物，左边没有：则只累加左边的pd[i - 1][j]数组的值；

3、相反，则只累加上方dp[i][j - 1]；

4、同时出现障碍物时，dp[i][j]设置为0；

5、没有障碍物，就正常相加；

（4）遍历顺序：

也是从[1][1]开始遍历，从浅带到深；

（5）打印dp数组（debug）；

2、整体代码如下：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        // 获得行数和列数
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) return 0;
        // 1、确定dp数组，和上一题类似；
        vector<vector<int>> dp(m, vector<int>(n));
        // 2、同样的方法初始化
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                for (int j = i; j < m; j++) {
                    dp[i][0] = 0;
                }
                break;
            }
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                for (int i = j; i < n; i++) {
                    dp[0][j] = 0;
                }
                break;
            }
            dp[0][j] = 1;
        }
        // 3、遍历顺序
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 情况0：当前的坐标有障碍物
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                    continue;
                }
                // 情况1：左边出现障碍物
                if (obstacleGrid[i - 1][j] == 1 && obstacleGrid[i][j - 1] != 1) {
                    dp[i][j] = dp[i][j - 1];
                    // 情况2：上方出现障碍物
                } else if (obstacleGrid[i - 1][j] != 1 && obstacleGrid[i][j -1] == 1) {
                    dp[i][j] = dp[i - 1][j];
                    // 情况3：左右均有障碍物
                } else if (obstacleGrid[i - 1][j] == 1 && obstacleGrid[i][j -1] == 1){
                    dp[i][j] = 0;
                    // 情况4：没有障碍物
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                }
            }
        }
        // 5、打印dp数组
        // for (int i = 0; i < m; i++) {
        //     for (int j = 0; j < n; j++) {
        //         cout << dp[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        return dp[m - 1][n - 1];
    }
};

今日学习时间：1.5小时；

Nobody can stop me.

我无人可当！

文章来源地址https://www.toymoban.com/news/detail-850275.html

到了这里，关于代码随想录第39天 | 62.不同路径、 63. 不同路径 II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！