題目：不同路徑 II
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）旋奢。
機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）湃缎。
現(xiàn)在考慮網(wǎng)格中有障礙物岁忘。那么從左上角到右下角將會(huì)有多少條不同的路徑？
示意圖
網(wǎng)格中的障礙物和空位置分別用
1 和 0 來(lái)表示深员。
說(shuō)明：m 和 n 的值均不超過(guò) 100负蠕。
示例1:
輸入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
輸出: 2
解釋:
3x3 網(wǎng)格的正中間有一個(gè)障礙物。
從左上角到右下角一共有 2 條不同的路徑：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
思路
- 假設(shè)終點(diǎn)為
(i,j),達(dá)到終點(diǎn)的路徑為f(i,j)倦畅。 - 因?yàn)闄C(jī)器人只能向下或者向右運(yùn)動(dòng)遮糖，那么
f(i,j) = f(i-1,j)+f(i,j-1)。那么可以使用動(dòng)態(tài)規(guī)格來(lái)解決這個(gè)問(wèn)題叠赐。 - 如果當(dāng)前位置有障礙欲账，那么無(wú)法到達(dá)當(dāng)前位置
f(i,j)=0 - 可以使用滾動(dòng)數(shù)組思想優(yōu)化的數(shù)組為,使得空間復(fù)雜度從
O(mn)到O(m)
實(shí)現(xiàn)
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
n, m := len(obstacleGrid), len(obstacleGrid[0])
f := make([][]int, n)
for i := 0; i < n; i++ {
f[i] = make([]int, m)
}
if obstacleGrid[0][0] == 0 {
f[0][0] = 1
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if obstacleGrid[i][j] != 0 {
f[i][j] = 0
continue
}
if i-1 >= 0 && obstacleGrid[i-1][j] == 0 {
f[i][j] += f[i-1][j]
}
if j-1 >= 0 && obstacleGrid[i][j-1] == 0 {
f[i][j] += f[i][j-1]
}
}
}
return f[n-1][m-1]
}
