不同路径
62. 不同路径
一个机器人位于一个 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
动态规划，函数递归+备忘录
从 (0, 0) 到 (x, y) 有 dp(x, y) 条路径，结束条件+失败条件
class Solution {
// 备忘录
int[][] memo;
public int uniquePaths(int m, int n) {
memo = new int[m][n];
return dp(m - 1, n - 1);
}
// 定义：从 (0, 0) 到 (x, y) 有 dp(x, y) 条路径
int dp(int x, int y) {
// base case，结束和成功条件
if (x == 0 && y == 0) {
return 1;
}
// 失败条件：越界
if (x < 0 || y < 0) {
return 0;
}
// 避免冗余计算
if (memo[x][y] > 0) {
return memo[x][y];
}
// 状态转移方程：
// 到达 (x, y) 的路径数等于到达 (x - 1, y) 和 (x, y - 1) 路径数之和
memo[x][y] = dp(x - 1, y) + dp(x, y - 1);
return memo[x][y];
}
}时间复杂度和空间复杂度都是O(mn)
动态规划，数组迭代
dp[i][j]表示到达(i,j)的不同路径数量。
public int uniquePaths(int m, int n) {
// 如果网格的行数或列数为0，则不存在路径
if (m == 0 || n == 0) return 0;
// 初始化dp数组，dp[i][j]表示到达(i,j)的不同路径数量
int[][] dp = new int[m][n];
// 初始化第一行，因为机器人只能向右移动，所以第一行的每个格子的路径数都是1
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
// 初始化第一列，因为机器人只能向下移动，所以第一列的每个格子的路径数都是1
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
// 通过动态规划填充dp数组的其余部分
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// 到达(i,j)的路径数是从上方来和从左方来的路径数之和
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
// dp[m - 1][n - 1]存储的就是到达网格右下角的不同路径数量
return dp[m - 1][n - 1];
}- 时间复杂度:
O(mn)，因为需要填充整个dp数组。 - 空间复杂度:
O(mn)，因为需要使用一个dp数组来存储中间结果。
空间压缩
dp[j]表示更新前的dp[j]，即上一行的dp[j]，dp[j-1]表示左边的值
public int uniquePaths(int m, int n) {
// 初始化只有一行的dp数组
int[] dp = new int[n];
// 因为第一行的每个格子只有一种到达方式，初始化为1。
// 每一行的第一个格子的值也是1，所以下面的j从1开始而不是从0开始。重点。
Arrays.fill(dp, 1);
// 开始填充dp数组，从第二行开始。
for (int i = 1; i < m; i++) {
// 从第二列开始更新dp[j]，因为第一列保持第一列的值1即可
for (int j = 1; j < n; j++) {
// dp[j]表示更新前的dp[j]，即上一行的dp[j]，dp[j-1]表示左边的值
// 更新dp[j]为dp[j]（上方的值）加上dp[j-1]（左方的值）
dp[j] += dp[j - 1];
}
}
// 最后，dp[n - 1]存储到达最后一个格子的路径总数
return dp[n - 1];
}- 时间复杂度: O(mn)。
- 空间复杂度: O(n)。由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n 使得 m≤n，这样空间复杂度降低至 O(min(m,n))。
组合数学
从 m+n−2 次移动中选择 m−1 次向下移动的方案数
从左上角到右下角的过程中，我们需要移动 m+n−2 次，其中有 m−1 次向下移动， n−1 次向右移动。 因此路径的总数，就等于从 m+n−2 次移动中选择 m−1 次向下移动的方案数，即组合数:
Cm+n−2m−1=(m+n−2m−1)=(m−1)!(m+n−2)(m+n−3)⋯n=(m−1)!(n−1)!(m+n−2)!
class Solution {
public int uniquePaths(int m, int n) {
// 注意要用long
long ans = 1;
for (int x = n, y = 1; y < m; ++x, ++y) {
ans = ans * x / y;
}
return (int) ans;
}
}- 时间复杂度：O(m)。由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n 使得 m≤n， 这样空间复杂度降低至 O(min(m,n)) 。
- 空间复杂度: O(1)。