62不同路径

Posted on

不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？



例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

本题压缩了空间，下一层的dp只依赖上一层和当层前一个元素所以不用保存，所有dp状态，只需要一层dp值和记录的当前值就好啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func uniquePaths(m int, n int) int {
	//动态转移方程 F(m,n) = F(m,n-1)+F(m-1,n)\
	//F(m,n) =1 (m=0||n=0)
	fn := make([][]int,1)
	fn[0]= make([]int,n)
	pre := -1
	for i :=0;i<m;i++{
		for j:=0;j<n;j++{
			if i==0|| j==0{
				fn[0][j] = 1
			}else {
				fn[0][j] +=  pre
			}
			pre = fn[0][j]
		}
	}
	return fn[0][n-1]
}