leetcode 63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
题解：
1.m x n 网格
2.从左上角[0,0]到右下角[m-1,n-1]的可达路径
3.网格中有障碍物，挡住则不能成为一条可达路径
4.避开障碍物的情况下，有多少条可达路径
示例 1:
输入:
[[0,0,0],[0,1,0],[0,0,0]]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
解题思路：
-
递归向下、向右搜索
-
如果搜索到右下角并且不是障碍物则是一条可达路径，返回一个计数1
-
搜索范围超过矩阵长宽则是一条不可达路径返回0计数，遇到障碍物也是不可达返回0计数
-
单返回向下向右的递归和会超时，递归中实际上重复搜索计算了路径节点，使用一个二维数组记录中间计算结果，如果搜索过程中有重复直接返回值，节省了后续搜索时间；最后搜索结果仍要回到[0,0]
C/C++题解：
class Solution {
public:
vector<vector<int>> results;
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
vector<int> temp(obstacleGrid[0].size());
results.resize(obstacleGrid.size(),temp);
return dfs(0, 0, obstacleGrid);}
int dfs(int i, int j, vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
if (i == m - 1 && j == n - 1 && obstacleGrid[i][j] != 1) {
return 1;}//能到达最后一个位置，且不为障碍，则有一条可达路径
if (i >= m || j >= n || obstacleGrid[i][j] == 1) {
return 0;}//超出矩阵范围或遇到障碍物该条路径即不可达
if (results[i][j] != 0) {//备忘录记忆重复计算的值
return results[i][j];//递归时被计算过的直接返回数值，或者visited数组标志
}//减少运算，降低时间复杂度
//向下或向右递归搜索即可
results[i][j] = dfs(i + 1, j, obstacleGrid) + dfs(i, j + 1, obstacleGrid);
return results[i][j];}};//最终所有值返回(0,0)到终点的路径
Debug结果：
Java题解：
class Solution {
public int[][] results;
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
results = new int[obstacleGrid.length][obstacleGrid[0].length];
return dfs(0, 0, obstacleGrid);}
private int dfs(int i, int j, int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
if (i == m - 1 && j == n - 1 && obstacleGrid[i][j] != 1) {
return 1;}//能到达最后一个位置，且不为障碍，则有一条可达路径
if (i >= m || j >= n || obstacleGrid[i][j] == 1) {
return 0;}//超出矩阵范围或遇到障碍物该条路径即不可达
if (results[i][j] != 0) {//备忘录记忆重复计算的值
return results[i][j];//递归时被计算过的直接返回数值，或者visited数组标志
}//减少运算，降低时间复杂度
//向下或向右递归搜索即可
results[i][j] = dfs(i + 1, j, obstacleGrid) + dfs(i, j + 1, obstacleGrid);
return results[i][j];}}//最终所有值返回(0,0)到终点的路径
Debug结果：
Python题解：
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
""":type obstacleGrid: List[List[int]] :rtype: int"""
self.results = [[0 for _ in range(len(obstacleGrid[0]))] for _ in range(len(obstacleGrid))]
def dfs(i, j, obstacleGrid):
m, n = len(obstacleGrid), len(obstacleGrid[0])
if i == m - 1 and j == n - 1 and obstacleGrid[i][j] != 1:
return 1 #能到达最后一个位置，且不为障碍，则有一条可达路径
if i >= m or j >= n or obstacleGrid[i][j] == 1:
return 0 #超出矩阵范围或遇到障碍物该条路径即不可达
if self.results[i][j] != 0: #备忘录记忆重复计算的值
return self.results[i][j] #递归时被计算过的直接返回数值，或者visited数组标志
#减少运算，降低时间复杂度
#向下或向右递归搜索即可
self.results[i][j] = dfs(i + 1, j, obstacleGrid) + dfs(i, j + 1, obstacleGrid)
return self.results[i][j] #最终所有值返回(0,0)到终点的路径
return dfs(0, 0, obstacleGrid)
Debug结果：
更多题解移步公众号免费获取