Leetcode-62 Unique Paths

发表于 | 分类于 | 次

Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Constraints:

  • 1 <= m, n <= 100
  • It’s guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.

Example 1

1
2
3
4
5
6
7
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

解题思路

总共有 $C_{m+n-2}^{n-1}$ 条路经，但是直接计算将会越界。采用动态规划：要到达右下角 [m,n]，必须先到达 [m,n-1] 或 [m-1,n]，因此机器人到达每个位置的路径数等于到达其左边和上方位置的路径数之和。

复杂度分析

  • 时间复杂度：$O(mn)$。
  • 空间复杂度：$O(mn)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
	int uniquePaths(int m, int n) {
		vector<vector<int>> mp(m, vector<int>(n, 1));
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				mp[i][j] = mp[i - 1][j] + mp[i][j - 1];
			}
		}
		return mp[m - 1][n - 1];
	}
};