LeetCode 63 - Unique Paths II

作者 QIFAN 日期 2017-01-05
LeetCode 63 - Unique Paths II

原题链接: 63. Unique Paths II


题干

这是 LeetCode 62 - Unique Path 的延伸。

给定一个 m * n 的矩阵,但是其中 “1” 表示障碍,不能通过;“0” 表示可通过。只能往下走或者往右走。问从左上角 (0,0) 开始到右下角共有多少条不同路径?

m 和 n 不大于 100 。

思路

只要做一些小小的修改。同样设定一个 dp[m][n] 来记录到达 (i, j) 的路径数。

假设在 (i, j) 。
case 1 : nums[i][j] == 0dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
case 2 : nums[i][j] == 1dp[i][j] = 0 ,没有路径可以到达。

同样使用广度优先来遍历 dp 。

时间复杂度 $O(MN)$ ,空间复杂度 $O(MN)$ 。

代码:

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// 特殊情况
if (obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
return 0;
}
if (obstacleGrid[0][0] == 1) {
return 0;
}
int M = obstacleGrid.length;
int N = obstacleGrid[0].length;
int[][] dp = new int[M][N];
dp[0][0] = 1;
// 广度优先搜索
for (int step = 1; step <= M + N; step++) {
int i = 0;
int j;
if ((j = step - i) >= N) {
j = N - 1;
i = step - j;
}
while (i < M && j >= 0) {
if (obstacleGrid[i][j] == 0) {
if (i == 0) {
dp[i][j] = dp[i][j - 1];
} else if (j == 0) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
i++;
j = step - i;
}
}
return dp[M - 1][N - 1];
}

Can we do better?
空间上,可以取巧的不新建 dp ,直接赋值到原来的给定的二维数组,那样空间复杂度就是 $O(1)$ 。