-
63. 不同路径 II
-
解法同上,需要考虑障碍物
- 初始化的时候 当发现边界出现障碍物,之后的数据也不能置1
- dp生成值时,当无障碍物时,才生成
package algor.trainingcamp;
/**
* @author lizhe
* @version 1.0
* @description:
* 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
* 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
* 问总共有多少条不同的路径?
*
* 机器人每次只可以向右 或者 向下 (每次向右走 )
* dp[i][0] = 1;
* dp[0][j] = 1;
*
* dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
*
* i的范围 [0,m - 1]
* j的范围 [0,n - 1]
* @date 2023/5/13 19:17
*/
public class LeetCode62 {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i = 0;i < m;i++){
dp[i][0] = 1;
}
for(int i = 0;i < n;i++){
dp[0][i] = 1;
}
for(int i = 1;i < m;i++){
for(int j = 1;j < n;j++){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
package algor.trainingcamp;
/**
* @author lizhe
* @version 1.0
* @description: 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
* 网格中的障碍物和空位置分别用 1 和 0 来表示。
* 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
* <p>
* 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
* @date 2023/5/13 19:29
* <p>
* 解法和62相同,多了障碍处理
* 1. 初始化边界
* 从(0, 0)的位置到(i, 0)的路径只有一条,所以dp[i][0]一定为1,dp[0][j]也同理。
* 但如果(i, 0) 这条边有了障碍之后,障碍之后(包括障碍)都是走不到的位置了,所以障碍之后的dp[i][0]应该还是初始值0。
*
* 2. dp 数组生成时候 只考虑无障碍情况
* 3. 当d
*/
public class LeetCode63 {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
if(obstacleGrid[i][0] == 1){
break;
}else{
dp[i][0] = 1;
}
}
for (int i = 0; i < n; i++) {
if(obstacleGrid[0][i] == 1){
break;
}else{
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];
}
}