算法Day39 | 62. 不同路径，63. 不同路径 II-Toy模板网

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

62. 不同路径

题目链接：62. 不同路径
dp[i][j]结果为从起点到该点有多少路径。
递归公式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
初始化：因为只能从上往下、从左往右走，因此最上侧，最左侧初始化为1（1种路径）
遍历顺序：从上往下，从左往右

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        for (int i = 0; i < m; ++i) dp[i][0] = 1;
        for (int j = 0; j < n; ++j) dp[0][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.back().back();
    }
};

也可以使用滚动（一维）数组。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n);
        for (int i = 0; i < n; i++) dp[i] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp.back();
    }
};

其中 dp[j] 表示到达第 i 行第 j 列时的路径数目。由于每个格子只能从上面或左边走过去，所以 dp[j] 是由上面的格子 dp[j] 和左边的格子 dp[j - 1] 的路径数之和得到的。

63. 不同路径 II

题目链接：63. 不同路径 II
遇上一题不同之处为排除一下障碍物

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] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp.back().back();
    }
};

使用滚动数组，和上一题一样的思路，dp 数组中的每一个数表示这一列和之前的所有列的总和。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        vector<int> dp(obstacleGrid[0].size());
        //初始化
        for (int j = 0; j < dp.size(); ++j)
            if (obstacleGrid[0][j] == 1)
                dp[j] = 0;//
            else if (j == 0)
                dp[j] = 1;
            else
                dp[j] = dp[j-1];
		
        for (int i = 1; i < obstacleGrid.size(); ++i)
            for (int j = 0; j < dp.size(); ++j){
                if (obstacleGrid[i][j] == 1)
                    dp[j] = 0;
                else if (j != 0)
                    dp[j] = dp[j] + dp[j-1];
            }
        return dp.back();
    }
};

第一个 for 循环：遍历第一行，从第一个元素到最后一个元素逐一判断。如果当前元素为障碍物，则将该位置路径数置为0。如果当前元素不是障碍物且不是第一个元素，则将该位置的路径数取前一个位置的路径数。如果当前元素不是障碍物且是第一个元素，则将该位置的路径数赋为1

第二个 for 循环：这段代码使用两个 for 循环遍历从第二行开始的所有行和所有列。对于当前位置，如果它是障碍物，则该位置路径数为 0；否则，将当前位置的路径数更新为上一个位置和左一个位置路径数之和。文章来源地址https://www.toymoban.com/news/detail-498342.html

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