原题连接:leetcode63:不同路径II
先贴出题解的正确通过的代码:
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0) {
return 0;
}
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m&&obstacleGrid[i][0] == 0; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n&&obstacleGrid[0][j] == 0; j++) {
dp[0][j] = 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];
}
第二个是我自己写的,只有一个地方不同,那就是前两个循环中题解是在for循环语句这一行中做了判断,而我是另外用if语句做了判断
两个代码的运行结果却不一致,没搞明白是为什么?
public int uniquePathsWithObstacles(int[][] obstacleGrid){
if (obstacleGrid == null || obstacleGrid.length == 0) {
return 0;
}
int m=obstacleGrid.length,n=obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
if(obstacleGrid[i][0]==0)
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
if(obstacleGrid[0][i]==0)
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];
}
结果不一致的输入样例如下:
{{0,0},{1,1},{0,0}}
正确答案是0,而第二个代码运行结果为1 ,没想明白是什么原因
那肯定不一样的啊。
第一种写法的循环终止条件是两个,你写的循环终止条件是一个。好好理解一下。
对于第一种写法:如果循环终止条件是判断不满足就不会执行。
对于第二种写法:会依然执行,因为第一个循环判断成立,只是内部的if条件不成立。
这个循环不一样,取到的值不同了。
for (int j = 0; j < n&&obstacleGrid[0][j] == 0; j++) {
dp[0][j] = 1;
}
主要看循环条件:正确代码
// 二维数组{{1,0}} j定义为0 n的长度为2 必须满足条件是j<2 也就是0<2 为true
// 且obstacleGrid[0][j] == 0 也就是obstacleGrid[0][0] == 0 条件不满足 为false 是不会进入for循环 在入口就给终止
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
dp[0][j] = 1;
}
错误代码:
// 二维数组{{1,0}} i定义为0 n的长度为2 必须满足条件是i<2 也就是0<2 为true
// 进入循环 第一次obstacleGrid[0][i] == 0条件为false 因为这个下标的值是1 进入第二次循环 i=1的时候 obstacleGrid[0][i] == 0条件为true
// 改变dp[0][i] == 1的值 这个循环是会进入且循环完毕 找到满足条件的就进行改值
for (int i = 0; i < n; i++) {
if (obstacleGrid[0][i] == 0)
dp[0][i] = 1;
}
两者之间区别在于 第一个循环会在条件位置给你终止循环 让你进不去 第二次循环是进去了 每次循环都在找符合条件的机会进行改值