代码随想录算法训练营第三十四天-动态规划-63. 不同路径II

• 本题与上一题区别不大
• 但由于存在障碍格，导致在计算路径值时，要多考虑一些情况
  • 比如，障碍格在开始与结束位置时，路径直接返回0
  • 障碍格在初始的首行与首列时，设置初始值要不同
  • 在计算dp值时，要先判断当前格是不是障碍格

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;
        }
        int dp[m][n];
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n && obstacleGrid[0][i] != 1; ++i) {
            dp[0][i] = 1;
        }
        for (int i = 0; i < m && obstacleGrid[i][0] != 1; ++i) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (obstacleGrid[i][j]) {
                    continue;
                }
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};

• 在运行代码时报了一个错，在17和18行时，出发位置没有设置从1开始，会导致22行出现数组越界情况
• 汇总