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 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
思路1：
一上去就觉得是简单题：
如果当前格位于第m行或第n列，则只有一种路径；
否则当前格路径数等于“右格路径数”+“下格路径数”；
代码（未AC）：
class Solution {
public:
int uniquePaths(int m, int n) {
if (m == || n == )
return ;
return uniquePaths(m - , n) + uniquePaths(m, n - );
}
};
结果提示超时了。
思路2：
考虑超时原因很可能是使用了函数递归，为避免使用递归，新建一个m*n的矩阵空间用于保存每个点计算的路径数。用新建空间保存结果，代替递归。
代码（AC）：
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int> > grid(m, vector<int>(n, ));
for (int i = ; i < m; ++i) {
for (int j = ; j < n; ++j) {
grid[i][j] = grid[i-][j] + grid[i][j-];
}
}
return grid[m-][n-];
}
};
思路3：
上述代码时间复杂度o(m*n)，空间复杂度o(m*n)，通过观察路径数量规律，还可以减少空间复杂度为o(n)。
已知grid[i][j] = grid[i-1][j] + grid[i][j-1];
进一步将后一项grid[i][j-1]替换为grid[i-1][j-1] + grid[i][j-2];
不断查分后一项，最终grid[i][j] = grid[i-1][j] + grid[i-1][j-1] + grid[i-1][j-2] + ... + grid[i-1][1] + grid[i][0];
又因为grid[i][0] = grid[i-1][0] = 1；
所以grid[i][j] 就等于第i-1行，从0到j所有元素之和；
得到了这个规律，我们只需要一个长度为n的数组col，通过第0行计算第1行，并不断迭代，最终得到第m行格子存在的路径数，此时col[n-1]即为所求.
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> col(n, );
for (int i = ; i < m; ++i) {
for (int j = ; j < n; ++j) {
col[j] = col[j-] + col[j];
}
}
return col[n-];
}
};
思路4：
可以通过分析排列组合暴力求解：
从格子起始，一共需要移动n+m-2步，可以到达终点。
这n+m-2步中，有m-1步需要向下移动。
问题转化为，从n+m-2步中，选择m-1步向下移动，有多少种选择方法。
因此通过计算Combination(n+m-2, m-1)即可求得答案.
代码（超时）：
class Solution {
public:
int uniquePaths(int m, int n) {
long long dividend = ;
long long divisor = ;
for (int i = ; i <= m - ; ++i) {
dividend *= i + n - ;
divisor *= i;
}
return int(dividend / divisor);
}
};
代码超时，未AC，正要放弃，看了讨论区的代码..原来用浮点数直接除，结果是正确的；
即（代码AC）：
class Solution {
public:
int uniquePaths(int m, int n) {
double res = ;
for (int i = ; i <= m - ; ++i) {
res = res * (i + n - ) / i;
}
return int(res);
}
};