没有障碍物的时候

选择立扣第 62 题

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

分析

原问题和子问题

可以使用动态规划的方法来求解这个题。求 m,n是连个束缚条件，所以原问题和子问题为：

1. 原问题： 在 m*n 的格子中，能有多少路径
2. 子问题： 在 i*j 的格子里，能有多少路径

状态

在原问题，还有子问题的分析中，i,j 两个是自变量，所以他们两个可以当成是状态

状态转移方程

父问题和子问题的关系：

  f(x,y)=f(x-1,y)+f(x,y-1)

动态数组

dp[i][j] 一般状态就是动态数组的下标。

代码

func uniquePaths(m int, n int) int { //总共有m，n个格子
	dp := make([][]int, m) //先声明dp数组
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
	}
	dp[0][0] = 0 //从1开始的话，就0步
	for i := 0; i < n; i++ {
		dp[0][i] = 1
	}
	for j := 0; j < m; j++ {
		dp[j][0] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m-1][n-1]
}

有障碍的格子

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

代码

一定要注意，下面的那些错误。

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	dp := make([][]int, len(obstacleGrid))
	m, n := len(obstacleGrid), len(obstacleGrid[0])
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
	}
	dp[0][0]=1 // 0,0 这种情况，一定要单独考虑
	for i := 1; i < m; i++ {
		if obstacleGrid[i][0] == 1 {
			break
		}
		dp[i][0] = 1
	}

	for j := 1; j < m; j++ {
		if obstacleGrid[0][j] == 1 {
			break
		}
		dp[0][j] = 1 // 到底第几个是i，第几个是j，一定要看清
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if obstacleGrid[i][j] == 1 {
				dp[i][j] = 0
				continue
			}
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m-1][n-1]
}

立扣原题

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