文章目录

• 题目
• 思考
• 代码和注释
• 总结

题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思考

• 1、这题和路径I无非两点差距
  • a:初始化不一样，就是在头部的行和左边的列当我们遇到障碍时后面就都是0了
  • b：就是开始走动态方程的条件是，当前位置没有障碍才执行

代码和注释

/**动态规划：1、dp[i][j] 表示的是在当前点我们要的有几种方式2、动态方程 dp[i][j] = dp[i - 1][j]+dp[i][j-1]3、初始化4、遍历顺序5、log*/
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;//如果在起点或终点出现了障碍，直接返回0if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {return 0;}// 定义动态数组int[][] dp = new int[m][n];// 初始化(有障碍的情况，后面就都不能走了)for(int i = 0; iif(dp[0][i] == 0){dp[0][i]=1;}else{// 后面都是默认值0就行了break;}}for(int j = 0; jif(dp[j][0] == 0){dp[j][0]=1;}else{break;}}// 遍历for(int i = 1; ifor(int j = 1; j// 判断是不是有障碍if(obstacleGrid[i][j] == 0){dp[i][j] = dp[i-1][j] + dp[i][j-1];}else{dp[i][j] = 0;}}}return dp[m-1][n-1];}
}

总结

我说句题外话，就是何时使用【回溯】，何时使用【动态规划】，用大白话说，就是：

首先看取值范围，递归回溯一维数组，100就是深度的极限了（何况本题是100²）
如果是求走迷宫的【路径】，必然是回溯；如果是走迷宫的【路径的条数】，必然是dp--------(这个竟然屡试不爽！！！！)

a 稍微更正一下，那个如果将本题条件换成上下左右四个方向都能走的话，那就是回溯了，这就是走迷宫的过程。但如果是走迷宫的话，(限定往下和往右)，dp也是可以求路径的，做个记录就行了。(个人理解，如有问题，欢迎讨论。) o(￣▽￣)ブ