【Leetcode】63. 不同路径 II
【Leetcode】63. 不同路径 II
Leetcode名企之路
发布于 2018-09-12 15:19:44
发布于 2018-09-12 15:19:44
题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右题解
这个题目是第62题的加强版本,这个用数学的方式我觉得应该是不好解的。我们用DP的方式来解。 这里只是加了障碍物而已。再回顾一下上一次我们优化过后的DP:
class Solution {
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}
int[] res = new int[n];
res[0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 1; j < n; j++) {
res[j] += res[j - 1];
System.out.println("i=" + i + "_" + "j=" + j + ":" + Arrays.toString(res));
}
}
return res[n - 1];
}
}这个题中什么条件变了呢? 如果遇到障碍物,这列之前的所有路径都得归零;
java版本
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[] res = new int[n];
res[0] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (obstacleGrid[i][j] > 0) {
res[j] = 0;
} else if (j > 0) {
res[j] += res[j - 1];
}
}
}
return res[n - 1];
}
}python版本
class Solution(object):
def uniquePathsWithObstacles(self, Grid):
"""
:type Grid: List[List[int]]
:rtype: int
"""
m, n = len(Grid), len(Grid[0]) if Grid else 0
res = [1] + [0] * (n - 1)
for i in range(m):
for j in range(n):
if Grid[i][j] > 0:
res[j] = 0
elif j > 0:
res[j] += res[j - 1]
print(str(i) + '-' + str(j) + ":" + str(res))
return res[-1]这里还是按照惯例,模拟一个例子,看DP的状态数组,方便大家理解。
x = [
[0, 0, 0],
[0, 1, 0],
[0, 0, 0]
]状态更新为:
i=0 j=0:[1, 0, 0]
i=0 j=1:[1, 1, 0]
i=0 j=2:[1, 1, 1]
i=1 j=0:[1, 1, 1]
i=1 j=1:[1, 0, 1]
i=1 j=2:[1, 0, 1]
i=2 j=0:[1, 0, 1]
i=2 j=1:[1, 1, 1]
i=2 j=2:[1, 1, 2]当遇到1的时候,这一列的状态清零,代表从这列过的路径全部是不行的.
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-09-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录