题目链接:https://leetcode-cn.com/problems/unique-paths/
难度:中等
题目描述
一个机器人位于一个 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
题解
【方法一】:动态规划
时间复杂度:
空间复杂度:
机器人只能向右/向下走,所以若想到达第i行,第j列的位置,只有两种走法:
- 从第i-1行 第j列向下走一步;
- 从第i行,第j-1列向右走一步。
如下图:
那么我们设一个数组map[m, n],其中map[i][j]表示到达第i行第j列位置的路径数量。则有递推公式:。特殊情况,当只有一行或一列时,只有一种路径(即走直线)。
到这里,大家肯定也想到了用递归(代码如下),但是,用递归会有很多重复计算,本人提交试了一下,直接超时。
超时的递归代码:
class Solution {
public int uniquePaths(int m, int n) {
return cal(m, n, 0, 0);
}
private int cal(int m, int n, int row, int col){
if (row + 1 == m || col + 1 == n)
return 1;
return cal(m, n, row+1, col) + cal(m, n, row, col+1);
}
}
正确的Java代码:
class Solution {
public int uniquePaths(int m, int n) {
int[][] map = new int[m+1][n+1];
for (int i = 1; i <= n; i++) // 第一行初始化为1
map[1][i] = 1;
for (int i = 1; i <= m; i++) // 第一列初始化为1
map[i][1] = 1;
for (int i = 2; i <= m; i++)
for (int j = 2; j <= n; j++)
map[i][j] = map[i-1][j] + map[i][j-1]; // DP
return map[m][n];
}
}
【方法二】:组合数
时间复杂度:
空间复杂度:
因为机器人只能向右或向下走,所以到达第(m,n)处,需要向右走n-1步,向下走m-1步,一共走m+n-2步。因此路径的总数,就是从m+n-2步中选择m-1次向下走的方案数,即组合数:
计算的时候,我们可以使用m和n中最小的一个,更加节省时间。
代码如下:
class Solution {
public int uniquePaths(int m, int n) {
long ans = 1; // 注意这个地方,用int会溢出
if (m > n){ // 取m为较小的一个
int tmp = m;
m = n;
n = tmp;
}
for (int i = n, j = 1; j < m; i++, j++) // 计算组合数
ans = ans * i / j;
return (int)ans;
}
}