问题描述
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and space is marked as 1 and 0 respectively in the grid.
Example 1:
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0] ]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner:
- Right -> Right -> Down -> Down
- Down -> Down -> Right -> Right
Example 2:
Input: obstacleGrid = [[0,1],[0,0] ]
Output: 1
Constraints:
- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] is 0 or 1.
问题分析
问题比较简单，根据题意， 一般地，对于grid[row][col]，能够到达这个点只有2条路径： grid[row-1][col], grid[row][col-1]； 而如果grid[row][col]是障碍的话，能够到达这个点的路径方式就是0
那么综上，使用dp方式去求解，示例代码如下: (注意边界即可)
示例代码
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
rows := len(obstacleGrid)
cols := len(obstacleGrid[0])
dp := make([]int, rows*cols)
// base case
dp[0] = obstacleGrid[0][0] ^ 1
for row := 0; row < rows; row++ {
for col := 0; col < cols; col++ {
// 如果是起始点或者存在障碍物，无需更新dp值，默认为0
if (row == 0 && col == 0) || obstacleGrid[row][col] == 1 {
continue
}
top, left := 0, 0
// 到达上方的点的路径数量
if row > 0 {
top = dp[(row-1)*cols+col]
}
// 到达左侧的点的路径数量
if col > 0 {
left = dp[row*cols+col-1]
}
dp[row*cols+col] = top + left
}
}
return dp[len(dp)-1]
}