LeetCode062（机器人的不同路径）

发表于 | 分类于 ，

题目：

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

思路：

　　根据题意，设机器人走到m,n处总共有f(m,n)条不同的路径。则f(m,n)=f(m-1,n)+f(m,n-1)。由此递推式即可写出动态规划代码。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// DP
   public int uniquePaths(int m, int n) {
	int[][] count = new int[m][n];
	for(int i = 0;i < m;i++) {
		count[i][0] = 1;
	}
	for(int i = 0;i < n;i++) {
		count[0][i] = 1;
	}
	for(int i = 1;i < m;i++) {
		for(int j = 1;j < n;j++) {
			count[i][j] = count[i-1][j] + count[i][j-1];
		}
	}
	return count[m-1][n-1];
   }

复杂度分析：

动态规划：

　　时间复杂度：
　　　　O(n2)。
　　空间复杂度：
　　　　O(n2)。

原题链接：

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