尧图网站建设 
63. 不同路径 II - 力扣LeetCode题目一个机器人位于网格左上角网格里存在障碍物obstacleGrid[i][j]1代表该位置有障碍物不能通行。机器人只能向下、向右走求从左上角走到右下角一共有多少路径。障碍物位置无法经过。思路解析状态转移和无障碍物版本几乎一样\(dp[i][j] dp[i-1][j]dp[i][j-1]\)增加一条规则如果当前网格位置存在障碍物dp[i][j]0代表到达该点路径数为 0后面的格子也不会从这里继承路径。初始化技巧沿用dp[0][1]1简化第一行第一列边界处理。class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int mobstacleGrid.size(); int nobstacleGrid[0].size(); vectorvectorintdp(m2,vectorint (n2,0)); dp[0][1]1; for(int i1;im1;i) { for(int j1;jn1;j) { dp[i][j]dp[i-1][j]dp[i][j-1]; if(obstacleGrid[i-1][j-1]1) dp[i][j]0; } } return dp[m][n]; } }; 算法日常・每日刷题--＜动态规划＞6
63. 不同路径 II - 力扣LeetCode题目一个机器人位于网格左上角网格里存在障碍物obstacleGrid[i][j]1代表该位置有障碍物不能通行。机器人只能向下、向右走求从左上角走到右下角一共有多少路径。障碍物位置无法经过。思路解析状态转移和无障碍物版本几乎一样\(dp[i][j] dp[i-1][j]dp[i][j-1]\)增加一条规则如果当前网格位置存在障碍物dp[i][j]0代表到达该点路径数为 0后面的格子也不会从这里继承路径。初始化技巧沿用dp[0][1]1简化第一行第一列边界处理。class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int mobstacleGrid.size(); int nobstacleGrid[0].size(); vectorvectorintdp(m2,vectorint (n2,0)); dp[0][1]1; for(int i1;im1;i) { for(int j1;jn1;j) { dp[i][j]dp[i-1][j]dp[i][j-1]; if(obstacleGrid[i-1][j-1]1) dp[i][j]0; } } return dp[m][n]; } };