题目大意：
一个机器人位于一个 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深度优先搜索之间的关系。如果你看过我总结的 LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(下) 这篇文章，你应该记得看到这种格子或者矩阵应该下意识想到使用dfs，本题也很明确的指出需要求解路径数量，那么显然就是为了dfs算法量身定做的题目。
解法一：DFS深度优先搜索
在起点和终点已经固定的情况下，是dfs中比较简单的一类。我们只需按照规则进行移动即可。我们定义一个递归函数dfs()用于模拟路径搜索，递归方法的返回值为从当前格子出发到达终点的路径数。对于每个格子，只能向下或者向右移动，因此当前位置到达终点的可能性一定是dfs(相邻下方格子) + dfs(相邻右方格子)。这里需要注意一下边界问题，在最下一行以及最右一列时只能向一个方向移动。对于终点位置，它到终点的方式只有原地不动这一种选择，因此直接返回1即可，这也是递归方法的结束。
最后再来考虑记忆数组，很明显，我们只要记住每一次递归方法的结果即可，即当前格子到达终点的路径个数。使用记忆数组的目的在于避免重复计算。
上代码～
class Solution {
int[][] memo; // 记忆数组
public int uniquePaths(int m, int n) {
memo = new int[m][n]; // 初始化记忆数组
return dfs(0,0,m,n); // dfs走起
}
// x: 当前横坐标
// y: 当前纵坐标
int dfs(int x, int y, int m, int n){
if(x == m || y == n) return 0; // 越界时返回0
if(x==m-1 && y==n-1) return 1; // 终点位置直接返回1
if(memo[x][y]>0) return memo[x][y]; // 从记忆数组中读取已存在的数据，直接返回。
// dfs(相邻下方格子) + dfs(相邻右方格子)是当前结果
int res = dfs(x+1, y, m, n) + dfs(x,y+1, m, n);
memo[x][y] = res; // 将当前结果保存至记忆数组
return res;
}
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths.Memory Usage: 35.8 MB, less than 74.48% of Java online submissions for Unique Paths.
解法二：DP动态规划
动态规划的想法和dfs是相反的，但是思路却大同小异。我们先定义一个dp数组（功能和dfs的记忆数组几乎一致），dp[x][y]代表从起点到当前点的路径个数。我们在这里做一个比较：
dfs方法中memo[x][y]代表当前位置到终点的路径个数，
dp方法中dp[x][y]代表起点位置到当前位置的路径个数。
可以看出，dp方法更像是正向推理，而dfs则是反向。
回到DP解法，接下来我们需要对dp数组进行初始化操作。通过观察可知，最上方的一行中，每个格子只能通过其左方格子到达，因此第一行中每个格子和起点间的路径只有一条，即dp[0][y] = 1。同理最左列格子和起点间也仅存在唯一路径过，即dp[x][0] = 1。最后再看其他格子，我们很明显可以得出一个规律，对于任意一个格子，路径上连接他的上一个位置只能是他相邻上方或右侧格子，因此，到达当前位置的可能性也就是dp[相邻左侧] + dp[相邻上侧]。最终dp[终点]既是返回结果。
实现代码：
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n]; // dp数组，dp[x][y]代表起点到当前位置的路径个数
for(int i=0;i<m;i++) dp[i][0]=1; // 初始化第一列都是1
for(int i=0;i<n;i++) dp[0][i]=1; // 初始化第一行都是1
for(int i=1;i<m;i++){ // 循环每一个点（第一行和第一列除外）
for(int j=1;j<n;j++){
// 起点到当前位置的可能性为dp[相邻左侧] + dp[相邻上侧]
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths.Memory Usage: 35.7 MB, less than 85.29% of Java online submissions for Unique Paths.
总结：
两种解法的时间复杂度几乎相同，正如上方提到的，只是思考的方式不同而已，对于正向思考或者是逆向思考哪个更容易理解，这必然因人而异，希望本文能够对你有所帮助。我们下篇文章再见！
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-62-unique-paths-解题思路分析（2种经典思路）/