63.不同路径II

63.不同路径II

题解

state: dp[x][y]从起点走到 x,y 的不同路径
function: dp[x][y] = dp[x-1][y], dp[x][y-1]
intialize: 第一行和第一列，没有障碍物的为1，有障碍物之后都为0
answer: dp[n-1][m-1]

代码

package mainfunc uniquePathsWithObstacles(obstacleGrid [][]int) int {dp := make([][]int, len(obstacleGrid))for i := 0; i < len(obstacleGrid); i++ {dp[i] = make([]int, len(obstacleGrid[i]))}for i := 0; i < len(obstacleGrid); i++ {if obstacleGrid[i][0] != 1 {dp[i][0] = 1} else {break}}for i := 0; i < len(obstacleGrid[0]); i++ {if obstacleGrid[0][i] != 1 {dp[0][i] = 1} else {break}}for i := 1; i < len(obstacleGrid); i++ {for j := 1; j < len(obstacleGrid[i]); j++ {if obstacleGrid[i][j] != 1 {dp[i][j] = dp[i-1][j] + dp[i][j-1]}}}return dp[len(obstacleGrid)-1][len(obstacleGrid[len(obstacleGrid)-1])-1]
}