目录
1，题目描述
2，思路
思路一：排列组合
思路二：动态规划
方法一：空间复杂度O(m*n)
方法二：空间复杂度O(2n)
方法三：空间复杂度O(n)
3，代码【C++】
4，运行结果
1，题目描述
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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2，思路
参考这位大神的文章！@powcai 动态规划，以下内容来对大神的思路进行详细的解释。
思路一：排列组合
学过排列组合的小伙伴们应该很清楚这类经典题型吧！
m*n的方格，只需要走（m - 1)+(n - 1) 步即可（曼哈顿距离），而要符合规则，只需保证（m+n-2）步中，有（m-1）步向右，（n-1）步向下即可，无需关心是那一步。
即
，等价于
，公式编辑如下：
思路二：动态规划
时间复杂度基本上都是O(n^2)
方法一：空间复杂度O(m*n)
首先，从起点到达最左边一列或是最上边一行的任意一点，均只有1种方法，故初始为1；
基本思路如图，要计算Dp[i][j]，只需知道Dp[i][j-1]与Dp[i-1][j]即可，Dp[i][j] = Dp[i][j-1] + Dp[i-1][j]（从红色块走到绿色块均只有一种方法，故直接相加即可）；
因此，只需声明一个m*n的矩阵数组，按照自上而下、自左至右的顺序将矩阵进行填充，即可算出最后答案；
动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
有同学可能注意到了，每次计算，都只用到了两行，即当前行和上一行，其余空间均未使用，所以就有了方法二！
方法二：空间复杂度O(2n)
声明两个数组，cur[n]和pre[n]，只记录两行内容，同样按照自上而下、自左至右的顺序计算；
由于第一行事先已经赋值为1，即已经具备了初始条件；
依次计算cur数组，计算完整一行后，将cur赋值给pre，重复此过程即可得出答案；
动态方程：cur[i] = cur[i-1] + pre[i]
然而大神绝不满足于此！注意到计算时是按照顺序从左向右进行的，计算cur[i]时，仍可利用原先存放在cur[i]的值！
方法三：空间复杂度O(n)
由于是按照顺序进行计算，在覆盖原值之前，仍可以对其进行利用！以此来代替pre数组。
动态方程：ans[i] += ans[i-1]
妙啊！给大佬递可乐！
3，代码【C++】
这里仅给出最简方法的代码。
class Solution {
public:
int uniquePaths(int m, int n) {
int ans[n];
//memset(ans,1,sizeof(ans));
for(int i = 0 ; i < n ; i++) ans[i]=1; //初始化边界为1
for(int i = 1 ; i < m ; i++){
for(int j = 1 ; j < n ; j++){
ans[j] += ans[j-1];
}
}
return ans[n-1];
}
};