一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為“Start” ）炊豪。
機器人每次只能向下或者向右移動一步磷仰。機器人試圖達到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）嘱巾。
現(xiàn)在考慮網(wǎng)格中有障礙物趟畏。那么從左上角到右下角將會有多少條不同的路徑蚜退？
image.png
網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示恢总。
示例 1：
image.png
輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
輸出：2
解釋：
3x3 網(wǎng)格的正中間有一個障礙物菩浙。
從左上角到右下角一共有 2 條不同的路徑：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
示例 2：
image.png
輸入：obstacleGrid = [[0,1],[0,0]]
輸出：1
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-paths-ii
解題思路
和上一題不同路徑思路基本一致
但是多了障礙判斷
并且為了節(jié)省空間, 采用一維滾動數(shù)組來代替二維數(shù)組
dp[j] += dp[j - 1]相當(dāng)于將[i - 1][j]的結(jié)果+= [i][j - 1]然后賦給[i][j]
因為矩陣中每個格子的路徑數(shù)只需要看上方或者左方
所以兩層循環(huán)時, 每次子循環(huán)時一維數(shù)組中原有的值代表了該位置i, j的上方i - 1, j的路徑數(shù)
然后再加上一維數(shù)組中元素的前一個元素的路徑, 代表了加上i, j - 1的路徑
最后返回一維數(shù)組最后一個元素
代碼
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid[0][0] == 1) {
return 0;
}
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[] dp = new int[n];
dp[0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
continue;
}
if (j >= 1) {
// 相當(dāng)于將[i - 1][j]的結(jié)果 += [i][j - 1]然后賦給[i][j]
// 滾動數(shù)組
dp[j] += dp[j - 1];
}
}
}
return dp[n - 1];
}
}
