代码随想录算法训练营第39天 | 62.不同路径, 63.不同路径 II

62.不同路径

代码随想录链接

题目

LeetCode-62.不同路径

在一个网格中, 机器人每次只能向下或向右移动一步, 求到达网格右下方有多少种走法.

自己的想法

对于一个网格来说, 到达这个位置的走法是到达上方位置的走法和左侧位置走法之和, 故有递推公式\[dp[i][j] = dp[i - 1][j] + dp[i][j - 1]\]

对于网格第一排和第一列的网格来说, 走法只有一种, 故\(dp[i][0]\)和\(dp[0][j]\)应该初始化为1.

题解

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

63.不同路径 II

代码随想录链接

题目

LeetCode-63.不同路径 II

与上面那题相似, 不过中间加了不可抵达的区域.

自己的想法

同样地处理方式就可以了, 不过就是在遇到障碍物时, 不计算障碍物的dp, 让其一直保持为0.

题解

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        if (obstacleGrid[0][0] || obstacleGrid[m - 1][n - 1])   // 起始位置为障碍物的话指定不行
            return 0;
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m && !obstacleGrid[i][0]; i++)      // 初始化第一列到有石头的位置
            dp[i][0] = 1;
        for (int j = 0; j < n && !obstacleGrid[0][j]; j++)      // 初始化第一列到有石头的位置
            dp[0][j] = 1;
        for (int i = 1; i < m; i++)                             // 递推计算dp
            for (int j = 1; j < n; j++)
                if (obstacleGrid[i][j]) continue;               // 有石头的地方保持为0
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m - 1][n - 1];
    }
};