北京网站制作培训学校网站设计开发网站

• 本题与上一题区别不大
• 但由于存在障碍格，导致在计算路径值时，要多考虑一些情况
  • 比如，障碍格在开始与结束位置时，路径直接返回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行出现数组越界情况
• 汇总