0063.不同路径 II

https://leetcode.cn/problems/unique-paths-ii/

方法一：动态规划

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(n)$ ，其中 m 和 n 分别表示 obstacleGrid 数组的行数和列数。


func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	dp, m, n := make([]int, len(obstacleGrid[0])), len(obstacleGrid), len(obstacleGrid[0])

	for i := 0; i < n && obstacleGrid[0][i] != 1; i++ {
		dp[i] = 1
	}

	for i := 1; i < m; i++ {
		for j := 0; j < n; j++ {
			if obstacleGrid[i][j] == 0 {
				if j > 0 {
					dp[j] += dp[j-1]
				}
			} else {
				dp[j] = 0
			}
		}
	}
	return dp[n-1]
}