有关做橡胶品的网站,巴塘网站建设,wordpress首页固定页面,网站例子2023.8.9 这题是不同路径I的升级版#xff0c;在路径上增加了障碍物#xff0c;有障碍物的地方无法通过。 我的思路依然还是使用动态规划#xff0c;dp[i][j]的含义依然是到#xff08;i#xff0c;j#xff09;这个位置的路径个数。只需要在dp数组中将有障碍物的地方赋为…2023.8.9 这题是不同路径I的升级版在路径上增加了障碍物有障碍物的地方无法通过。 我的思路依然还是使用动态规划dp[i][j]的含义依然是到ij这个位置的路径个数。只需要在dp数组中将有障碍物的地方赋为0。大致步骤如下
先进行极端情况判断当起始位置为障碍物时无法到达终点直接返回0。然后对第一行和第一列进行初始化有障碍物的地方赋为0无障碍物的地方赋为其左方或者上方的值。用两个for循环递推赋值递推公式和不同路径I 一样当前位置的路径个数 上方位置路径个数 左方位置的路径个数。 代码如下
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {if(obstacleGrid[0][0] 1) return 0; //起点就是障碍物int m obstacleGrid.size();int n obstacleGrid[0].size();vectorvectorint dp(m , vectorint(n));dp[0][0] 1;//第一行初始化赋值for(int i1; in; i){//有障碍物if(obstacleGrid[0][i] 1) dp[0][i] 0;//无障碍物else dp[0][i] dp[0][i-1];}//第一列初始化赋值for(int i1; im; i){if(obstacleGrid[i][0] 1) dp[i][0] 0;else dp[i][0] dp[i-1][0];}//遍历递推赋值for(int i1; im; i){for(int j1; jn; 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];}
};
