欢迎访问LeetCode题解合集
题目描述
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1
和 0
来表示。
示例1:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例2:
输入:obstacleGrid = [[0,1],[0,0]]
输出:1
提示:
-
m == obstacleGrid.length
-
n == obstacleGrid[i].length
-
$1 \le m, n \le 100$
-
obstacleGrid[i][j]
为0
或1
题解:
跟 不同路径 基本是一样的,f[i][j]
表示从 (0,0)
到 (i,j)
不同路径数目,因为此题增加了障碍物的条件,所以,转移方程需要改变一下。
初始时值都为零,表示所有都不可达,若 (0,0)
或 (n-1, m-1)
其中一个为 1
,就不可能到达右下角,直接返回 0
;否则的话,将 f[0][0]
置为 1
,表示有一条路径可达。假设当前来到 (i,j)
位置,分情况讨论:
-
若
(i, j)
位置为1
,直接跳过,障碍物肯定没法到达的 -
否则的话,
f[i][j] = f[i - 1][j] + f[i][j - 1]
时间复杂度:$O(n * m)$
额外空间复杂度:$O(n * m)$
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int n = obstacleGrid.size();
int m = obstacleGrid[0].size();
if( obstacleGrid[0][0] || obstacleGrid[n - 1][m - 1] ) return 0;
vector<vector<int>> f( n, vector<int>(m, 0) );
f[0][0] = 1;
for ( int i = 1; i < m; ++i ) {
if ( obstacleGrid[0][i] ) break;
f[0][i] = 1;
}
for ( int i = 1; i < n; ++i ) {
if ( obstacleGrid[i][0] ) break;
f[i][0] = 1;
}
for ( int i = 1; i < n; ++i ) {
for ( int j = 1; j < m; ++j ) {
if ( obstacleGrid[i][j] ) continue;
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[n - 1][m - 1];
}
};
/*
时间:0ms,击败:100.00%
内存:7.7MB,击败:88.50%
*/
使用滚动数组优化第一维,需要特殊处理每行第一个元素:
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int n = obstacleGrid.size();
int m = obstacleGrid[0].size();
if( obstacleGrid[0][0] || obstacleGrid[n - 1][m - 1] ) return 0;
vector<int> f(m);
f[0] = 1;
for ( int i = 0; i < n; ++i ) {
if ( obstacleGrid[i][0] ) f[0] = 0;
for ( int j = 0; j < m; ++j ) {
if ( obstacleGrid[i][j] ) {
f[j] = 0;
continue;
}
if ( j ) f[j] += f[j - 1];
}
}
return f[m - 1];
}
};
/*
时间:0ms,击败:100.00%s
内存:7.5MB,击败:93.33%
*/