网站主页制作,中山网站建设价格,活动策划网,定制开发微信小程序跟着carl学算法#xff0c;本系列博客仅做个人记录#xff0c;建议大家都去看carl本人的博客#xff0c;写的真的很好的#xff01; 代码随想录 LeetCode#xff1a;63. 不同路径 II 给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角#xff08;即 grid[0][0]… 跟着carl学算法本系列博客仅做个人记录建议大家都去看carl本人的博客写的真的很好的 代码随想录 LeetCode63. 不同路径 II 给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角即 grid[0][0]。机器人尝试移动到 右下角即 grid[m - 1][n - 1]。机器人每次只能向下或者向右移动一步。 网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含任何有障碍物的方格。 返回机器人能够到达右下角的不同路径数量。 测试用例保证答案小于等于 2 * 109。 示例 1 输入obstacleGrid [[0,0,0],[0,1,0],[0,0,0]] 输出2 解释3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径 向右 - 向右 - 向下 - 向下向下 - 向下 - 向右 - 向右 示例 2 输入obstacleGrid [[0,1],[0,0]] 输出1 需要注意初始化的代码 // 这种遇到障碍物则立即终止后面的都为0for (int i 0; i n obstacleGrid[0][i] 0; i) {dp[0][i] 1;}// 这种遇到障碍物还会继续向后遍历在这里面是错误的初始化方式for (int i 0; i n; i) {if (obstacleGrid[0][i] ! 1) {dp[0][i] 1;}}public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;int[][] dp new int[m][n];if (obstacleGrid[0][0] 1 || obstacleGrid[m - 1][n - 1] 1)return 0;for (int i 0; i m obstacleGrid[i][0] 0; i) {dp[i][0] 1;}for (int i 0; i n obstacleGrid[0][i] 0; i) {dp[0][i] 1;}for (int i 1; i m; i) {for (int j 1; j n; j) {if (obstacleGrid[i][j] 0) {dp[i][j] dp[i - 1][j] dp[i][j - 1];}}}return dp[m - 1][n - 1];}
