63.不同路径 II

题目链接：https://leetcode.cn/problems/unique-paths-ii/description/

解析：

使用动态规划，状态转移方程;

每个位置的状态取决于其上一个位置的状态，推到最底下，也就是 n-1,m-1 即是答案;

如果遇到障碍物，那么 dp[i][j]为 0; 如果是起点，为 1 其余情况，在上一个状态存在的情况下，+=上一个状态;

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	dp := make([][]int, len(obstacleGrid))
	for i := range dp {
		dp[i] = make([]int, len(obstacleGrid[i])+1)
	}
	for i := range len(obstacleGrid) {
		for j := range len(obstacleGrid[i]) {
			if obstacleGrid[i][j] == 1 {
				dp[i][j] = 0 // 障碍物为 0
			} else if i == 0 && j == 0 {
				dp[i][j] = 1 // 起始点为 1
			} else {
				if i > 0 {
					dp[i][j] += dp[i-1][j]
				}
				if j > 0 {
					dp[i][j] += dp[i][j-1]
				}
			}
		}
	}
	return dp[len(obstacleGrid)-1][len(obstacleGrid[0])-1]
}