题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
提示：
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 109
题目解析
题目是给出一个m*n的网格，有起点（start)和终点(finish)，一个机器人，从起点走向终点，每次只能向下或者向右走到达中终点，并且不能回退，问从起点到终点总共有几个方案。
我们以示例2画出图
算法原理讲解
1.状态表示
之前说过做题前得先有一个状态表示，而状态表示的确定，是经验+题目要求，根据之前的几个斐波那契额数列模型的题目，可以看出我们一般都是以某个位置为起点，或者以某一个位置为结尾，这道题我们选用常用的那个以某一个位置为结尾，另外这个是一个二维数组，所以我决定以[i，j]位置为结尾，并且题目要求从起点开始到结尾有多少条路径，因此我们将状态表示定义为，从起点到[i,j]位置的路径有dp[i][j]
2.状态转移方程
状态转移方程就是dp[i][j]等于什么，一般都是通过，状态表示来推出的，设一个[i,j]位置，然后根据最近的一步划分问题，
最近的一步，因为每次走，只能向右走一步，或者向下走一步，所以最近的位置有两个
a)[i-1,j]位置向下走一步达到[i,j]位置，如果要表示从起点到[i,j]位置的路径方式，先从起点走到[i-1,j]位置，再走一步达到[i,j]位置， 而从起点到[i-1,j]位置的路径方式，有dp[i-1][j],所以这种情况的dp[i][j]=dp[i-1][j];
b)[i,j-1]位置向右走一步达到[i,j]位置,同理a,这种情况下的dp[i][j]=dp[i][j-1]
最终从起点到[i,j]位置的路径的方式dp[i][j]就是这两种情况的相加
dp[i][j]=dp[i-1][j]+dp[i][j-1]
3.初始化
方法1
初始化是为了让填表的时候都不越界，首先我们得考虑填表需要什么呢？因为状态转移方程dp[i][j]=dp[i-1][j]+dp[i][j-1],所以填任何一个值都需要这个值左边的值和这个值上边的值，但是矩阵中
当i=0(第一行）时，没有上边的值，
当j=0(第一列）时，没有左边的值
所以初始化时，要初始化i=0和j=0时的值
根据状态转移方程，边界结点初始化的值应该都为1
方法2（虚拟节点）
接下来来介绍一个虚拟节点的方法，虚拟结点是增加需要的结点，然后给虚拟结点中填上合适的值，就可以将初始化的流程放在填表里面了
现在我们要在这些虚拟结点填值，并且保证虚拟结点里面的值，使后面的值都是正确的
还要注意 下标的映射，加了虚拟结点后，之前的矩阵的下标都 +1了
那虚拟结点应该填什么，才会让边界的值等于一呢，根据状态转移方程，每个格子都是，上面的格子里面的值，加上左边的格子里面的值，所以我们让原本的第一个格子的左边或者上边的值为1，其他全为0就行
4.填表顺序
从上往下，从左往右
5.返回值
如果初始化方法一返回dp[m-1][n-1]
如果初始化是方法二返回dp[m][n]
代码
初始化方法一
int uniquePaths(int m, int n) { //创建dp表 int dp[100][100]={0}; int i,j; //初始化 for(i=0,j=0;j<n;j++)dp[i][j]=1; for(i=0,j=0;i<m;i++)dp[i][j]=1; //填表 for(i=1;i<m;i++) { for(j=1;j<n;j++) { dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m-1][n-1]; }
空间复杂度:O(mn)
时间复杂度:O(mn)
初始化方法二
int uniquePaths(int m, int n) { //创建dp表 int dp[101][101]={0}; int i,j; //初始化 dp[1][0]=1; //填表 for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m][n]; }
空间复杂度:O(mn)
时间复杂度:O(mn)
