一个机器人位于一个 m * n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
https://leetcode-cn.com/problems/unique-paths/
示例1：
image输入：m = 3, n = 7
输出：28
示例2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
示例3：
输入：m = 7, n = 3
输出：28
示例4：
输入：m = 3, n = 3
输出：6
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10^9
Java解法
思路：
走一步回退一步算另一种，明显可以用回溯来处理。没想到超时了。。。但结果是正确的static int num = 0; public static int uniquePaths(int m, int n) { back(m,n,1,1); return num; } public static void back(int x, int y, int startX, int startY) { if (startX==x&&startY==y) { num++; return; } //向右 if (startX<x) { startX++; back(x, y, startX, startY); startX--; } //向下 是否能 if (startY<y) { startY++; back(x, y, startX, startY); } }考虑下其他算法，只能向右向下，就想m与n的不同排列组合（官方解2：组合数学）
image
public static int uniquePaths2(int m, int n) {
long ans = 1;
for (int x = n, y = 1; y < m; ++x, ++y) {
ans = ans * x / y;
}
return (int) ans;
}
image
官方解
https://leetcode-cn.com/problems/unique-paths/solution/bu-tong-lu-jing-by-leetcode-solution-hzjf/
-
动态规划
还能说什么。。666吧
public int uniquePaths(int m, int n) { int[][] f = new int[m][n]; for (int i = 0; i < m; ++i) { f[i][0] = 1; } for (int j = 0; j < n; ++j) { f[0][j] = 1; } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { f[i][j] = f[i - 1][j] + f[i][j - 1]; } } return f[m - 1][n - 1]; }- 时间复杂度：O(mn)
- 空间复杂度：O(mn)
-
组合数学
上述解法
- 时间复杂度：O(min(m,n))
- 空间复杂度：O(1)
