LeetCode算法系列（Java版） 62. 不同路径

LeetCode算法系列（Java版） 62. 不同路径
LeetCode算法系列（Java版） 63. 不同路径 II

力扣原题

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

方法一：动态规划

解题思路

我们用 表示从左上角走到 的路径数量，其中 和 的范围分别是 和 。

简单的说，在 m x n 网格中想要达到终点，向右几步，向下几步的范围是固定的。假设是 3 x 2 的网格，那向右2步，向下1步就能到达终点。即 就能达到终点。

由于我们每一步只能从向下或者向右移动一步，因此要想走到 ，如果向下走一步，那么会从 走过来；如果向右走一步，那么会从 走过来。因此我们可以写出动态规划转移方程：

因为中的是负数就没意义，所以我们需要排除一些边界值：

• 如果 ，那么 =1；（为什么等于1，说白了只能走直线）
• 如果 ，那么 =1；（为什么等于1，说白了只能走直线）
• 如果 ，，那么 =1；（其实也能等于0，原地不动怎么定义而已）

代码实现

class Solution {
    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];
    }
}

复杂度分析

• 时间复杂度：。

• 空间复杂度：，即为存储所有状态需要的空间。注意到 仅与第 行和第 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 。此外，由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 和 使得 ，这样空间复杂度降低至 。

方法二：排列组合

解题思路

上边我们用动态规划来解决问题，在求解（整体问题）的最优解的时候，后面的步骤选择只与当前状态有关，而与如何到达这个状态的步骤无关。如果一个决策的前面若干步骤已经确定从而进入某种状态之后，后面的步骤从按照当前状态开始的最优解必然是整体（包括该状态的情况下）的最优解，则该问题满足最优原理。

现在我们可以从整体出发来分析，从左上角到右下角的过程中，我们需要移动 次，其中有 次向下移动， 次向右移动。因此路径的总数，就等于从 次移动中选择 次向下移动（或 次向右移动）的方案数，即组合数：

代码实现

class Solution {
    public int uniquePaths(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }
}

复杂度分析

• 时间复杂度：。由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 和 使得 ，这样空间复杂度降低至 。

• 空间复杂度：。

LeetCode算法系列（Java版） 62. 不同路径
LeetCode算法系列（Java版） 63. 不同路径 II