一个机器人位于一个 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
解题思路：递归 -> 记忆化搜索 -> 动态规划
我们之前在讲动态规划的时候就已经写过这道题了，现在我们采用另一个思路，从递归推导到记忆化搜索再到动态规划！
首先就是递归解决，还是一样分三步走：
- 函数头的设计：
- 因为我们希望给
dfs()函数一个终点的坐标，就能求出从起点到终点的路径总和，所以要给两个参数m和n。然后返回值就是int类型，因为我们要求该递归函数直接算出结果给我们直接返回，而具体怎么处理我们并不关心！
- 因为我们希望给
- 函数体的内容：
- 我们以某个位置
(i, j)为参考，走到该位置只有两种可能，就是从上面走下来也就是(i-1, j)，和从左边走过来的也就是(i, j-1)，所以我们就能得到dfs(i , j)其实就是dfs(i-1, j) + dfs(i, j-1)来得到的，至于它又是怎么得到的，此时又会递归去得到它的结果，我们只需要关心其中一步即可！
- 我们以某个位置
- 函数递归出口：
- 因为有边界，所以只要当
i == 0或者j == 0的话就表示出界了，此时直接返回0即可！而当走到起点的时候，也就是i ==1 && j == 1的时候，就返回1。
- 因为有边界，所以只要当
class Solution {
public:
int uniquePaths(int m, int n) {
// 从终点往起点走
return dfs(m, n);
}
int dfs(int i, int j)
{
// 递归函数出口
if(i == 0 || j == 0)
return 0;
if(i == 1 && j == 1)
return 1;
return dfs(i - 1, j) + dfs(i, j - 1);
}
}; 虽然上面的代码没错，但是在跑用例的时候会超时，所以我们要进行优化，也就是看看能不能进行记忆化搜索！
判断能不能进行记忆化搜索，就是看有没有出现大量重复的问题，这道题很明显就能看到是有的，假设 i=4，j=4，那么此时 dfs(4, 4) 要去求 dfs(3, 4) 和 dfs(4, 3)，然后 dfs(3, 4) 要去求 dfs(2, 3) 和 dfs(3, 3)，而 dfs(4, 3) 要去求 dfs(3, 3)，此时就出现了重复的问题了，并且底下再展开还有更多的重复问题，如果数值越大的话重复的越多，所以可以使用记忆化搜索进行优化！
所以按照我们前面学的记忆化搜索的三个步骤，如下所示：
- 创建一个备忘录
- 在函数返回之前，将结果添加到备忘录中
- 在进入函数的时候，先判断该问题是否已经存在备忘录中
后两步是比较简单的，主要是第一步的创建备忘录，因为这道题可变参数有两个：i 和 j。所以我们得创建一个二维的备忘录，因为返回类型也是 int，所以我们可以搞一个二维数组作为备忘录！
剩下的两步就是添加一些细节，所以代码如下所示：
class Solution {
private:
int memory[101][101] = { 0 }; // 备忘录，初始化为0即可
public:
int uniquePaths(int m, int n) {
return dfs(m, n);
}
int dfs(int i, int j)
{
// 在进入函数的时候，先判断该问题是否已经存在备忘录中
if(memory[i][j] != 0)
return memory[i][j];
// 递归函数出口
if(i == 0 || j == 0)
return 0;
if(i == 1 && j == 1)
return 1;
// 在函数返回之前，将结果添加到备忘录中
memory[i][j] = dfs(i - 1, j) + dfs(i, j - 1);
return memory[i][j];
}
}; 跑用例马上就跑通了，并且速度是非常快的，从递归的超时到记忆化搜索的如此高效，说明这个优化是十分有效的！
下面我们尝试把记忆化搜索改为动态规划：
class Solution {
public:
int uniquePaths(int m, int n) {
// 创建dp表和初始化
int dp[101][101] = { 0 };
dp[1][1] = 1;
// 填表
for(int i = 1; i <= m; ++i)
{
for(int j = 1; j <= n; ++j)
{
// 如果是起点的话直接忽略
if(i == 1 && j == 1)
continue;
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}
}; 其中备忘录其实就是 dp 表，然后初始化就是递归函数出口的处理！至于填表过程，就是函数体的内容了，返回值就是函数返回值的意义！
