LeetCode 62. 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?

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

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
Example 2:

Input: m = 7, n = 3
Output: 28
解析：
给定一个格子，每次只能走一步，要么向由要么向下，计算所有可能的路径数量。
解法1:
从格子的左上(1,1)到右下(m,n)，实际上向右走了m-1步，向下走了n-1步，实际上总共走了m+n-2步，问题演化成走了m+n-2步，从中选择m-1步向右走，一个组合的问题。
具体看代码：

class Solution 
{
	public:
	int uniquePaths(int m, int n) 
	{
		int N = m+n-2;
		//所有的步数
		int k = m-1;
		//向右走的步数
		double res = 1;
		//Combination(N, k) = n! / (k!(n - k)!)
		//进行计算量的简化 C = ( (n - k + 1) * (n - k + 2) * ... * n ) / k!
		for (int i = 1; i <= k; i++) 
		{
			res = res * (N-k+i)/i;
		}
		return (int)res;
	}
}
;

解法2:
动态规划法，在任意一点(i,j)达到当前点的方式有两种：向下移动到达点(i,j)或者向右移动到达点(i,j)，假设到达当前点时的路径数量为path[i][j]，则有path[i][j]=path[i-1][j]+path[i][j-1]，对于边界：格子的最左边，此时path[i][j-1]不存在；格子的最上边，此时path[i-1][j]不存在。这两种情况下，路径数量只有一条，在初始化时为path[0][j]=1,path[i][0]=1，然后遍历的起始位置为1。
具体代码如下：

class Solution 
{
	public:
	int uniquePaths(int m, int n) 
	{
		vector< vector > path(m, vector(n,1));
		for (int i =1; i < m; i++) 
		{
			for (int j=1; j < n; j++) 
			{
				path[i][j] = path[i-1][j] + path[i][j-1];
			}
		}
		return path[m-1][n-1];
	}
}
;

时间复杂度为\(O(mn)\)，空间复杂度为\(O(mn)\)
解法2的优化：
我们考虑优化空间复杂度，解法2中使用了一个m*n的空间。在动态规划的递推公式中，我们发现path[i][j]=path[i-1][j]+path[i][j-1]，如果只关注列数的表示，path[i-1][j]与path[i][j]同列，而path[i][j-1]是path[i][j]的前一列。因此在计算当前数值时只需要维护当前列和前一列的数值即可。即path[j]=path[j-1]+path[j]。
代码如下：

class Solution 
{
	int uniquePaths(int m, int n) 
	{
		if (m > n) return uniquePaths(n, m);
		vector cur(m, 1);
		for (int j = 1; j < n; j++)
		for (int i = 1; i < m; i++)
		cur[i] += cur[i - 1];
		return cur[m - 1];
	}
}
;

参考：
https://leetcode.com/problems/unique-paths/discuss/22981/My-AC-solution-using-formula
https://leetcode.com/problems/unique-paths/discuss/22954/0ms-5-lines-DP-Solution-in-C++-with-Explanations