leetcode 63. 不同路径 II

2023.8.9

        这题是不同路径I的升级版，在路径上增加了障碍物，有障碍物的地方无法通过。

        我的思路依然还是使用动态规划，dp[i][j]的含义依然是到（i，j）这个位置的路径个数。只需要在dp数组中将有障碍物的地方赋为0。大致步骤如下：

• 先进行极端情况判断：当起始位置为障碍物时，无法到达终点，直接返回0。
• 然后对第一行和第一列进行初始化，有障碍物的地方赋为0，无障碍物的地方赋为其左方或者上方的值。
• 用两个for循环递推赋值，递推公式和不同路径I 一样，当前位置的路径个数 = 上方位置路径个数 + 左方位置的路径个数。  

        代码如下：

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {if(obstacleGrid[0][0] == 1) return 0; //起点就是障碍物int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<vector<int>> dp(m , vector<int>(n));dp[0][0] = 1;//第一行初始化赋值for(int i=1; i<n; i++){//有障碍物if(obstacleGrid[0][i] == 1) dp[0][i] = 0;//无障碍物else dp[0][i] = dp[0][i-1];}//第一列初始化赋值for(int i=1; i<m; i++){if(obstacleGrid[i][0] == 1) dp[i][0] = 0;else dp[i][0] = dp[i-1][0];}//遍历递推赋值for(int i=1; i<m; i++){for(int j=1; j<n; j++){if(obstacleGrid[i][j] == 1) dp[i][j] = 0; //有障碍物就不用赋值了else dp[i][j] = dp[i-1][j] + dp[i][j-1]; }}return dp[m-1][n-1];}
};