leetcode刷题（122）——62. 不同路径
一个机器人位于一个 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 <= m, n <= 100 obstacleGrid[i][j] 为 0 或 1
动态规划-1
对于动态规划，我们可以反过来想。 如何到达下图中橙色的(2,2)这个点。
只能由两个方向而来，上方、或者是左方；对于(3,2)障碍物这个点来说，能到达这里的路径就是0。 所以对于(i,j)这个点来说，其动态规划转移方程就是：
代码语言：javascript复制if 当前点不是障碍物：
dp[i][j] = dp[i - 1][j] dp[i][j - 1]
else:
dp[i][j] = 0我们还需要处理下边界情况，也就是第一列、第一行时
如上图，只要第一列中的某个格子是障碍物，那么这个格子跟后面的都无法到达。 同理，第一行中如果有格子是障碍物，那么这个格子跟后面的都无法到达了。 时间复杂度：O(M * N) 空间复杂度：O(M * N)
代码实现：
代码语言：javascript复制class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length;
int m = obstacleGrid[0].length;
int[][] dp = new int[n][m];
//(0,0)这个格子可能有障碍物
dp[0][0] = (obstacleGrid[0][0] == 1) ? 0 : 1;
//处理第一列
for(int i = 1; i < n; i) {
if(obstacleGrid[i][0] == 1 || dp[i - 1][0] == 0) {
dp[i][0] = 0;
} else {
dp[i][0] = 1;
}
}
//处理第一行
for(int j = 1; j < m; j) {
if(obstacleGrid[0][j] == 1 || dp[0][j - 1] == 0) {
dp[0][j] = 0;
} else {
dp[0][j] = 1;
}
}
for(int i = 1; i < n; i) {
for(int j = 1; j < m; j) {
//如果当前格子是障碍物
if(obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
//路径总数来自于上方(dp[i-1][j])和左方(dp[i][j-1])
} else {
dp[i][j] = dp[i - 1][j] dp[i][j - 1];
}
}
}
return dp[n - 1][m - 1];
}
}动态规划 空间优化
对于动态规划的两种解法，都是只需要上一层的解，而不需要上上一层的。
代码语言：javascript复制dp[i][j] = dp[i - 1][j] dp[i][j - 1]也就是求第i行时，只需要i-1行已求解过的值，不需要i-2行的了。 所以这里可以用滚动数组进行优化，将二维数组改为一维数组。 一维数组的大小为列的长度。
第三次迭代时，求第三个格子6时，由于左边的值已经是已知的，第二次迭代时同位置的值也是已知的。所以当前值的计算方式就是：
代码语言：javascript复制计算当前值 = 以求出的左边值 上一次迭代同位置的值
dp[j] = dp[j - 1] dp[j]时间复杂度：O(M * N) 空间复杂度：O(M)
代码实现：
代码语言：javascript复制class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length;
int m = obstacleGrid[0].length;
int[] dp = new int[m];
//起点可能有障碍物
dp[0] = (obstacleGrid[0][0] == 1) ? 0 : 1;
for(int i = 0; i < n; i) {
for(int j = 0; j < m; j) {
//有障碍物的格子直接赋0
if(obstacleGrid[i][j] == 1) {
dp[j] = 0;
}
//否则dp[j]的值由左方和上一次迭代的dp[j]累加而来
else if(obstacleGrid[i][j] == 0 && j - 1 >= 0) {
dp[j] = dp[j] dp[j - 1];
}
}
}
return dp[m - 1];
}
}
