【Leetcode 热题 100】62. 不同路径

问题背景

一个机器人位于一个 $m\times n$ 网格的左上角。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
问总共有多少条不同的路径？

数据约束

• $1\le m,n\le 100$
• 题目数据保证答案小于等于 $2\times 10^9$

解题过程

这是个显而易见的组合问题，对于每个用例，总共要移动的步骤数量是固定的 $(m+n-2)$，其中 $(m-1)$ 步要从上往下走，$(n-1)$ 步要从左往右走。
这样一来问题就转化成，有两种不同的选项，在 $(m+n-2)$ 个位置上分别填入 $(m-1)$ 个选项一和 $(n-1)$ 个选项二，问一共有多少种不同的结果。
答案是 $C_{m+n-2}^{m-1}$ 或 $C_{m+n-2}^{n-1}$，两者是等价的，该符号表示组合数的计算。
实现组合数，可以用两个索引来模拟数字增长的过程，抽象为累乘即可。
这样直接调用数学公式，时间复杂度是 $O(m)$ 这个量级的。

此外，还可以用动态规划的思路去理解。
对于每一个位置，它是由上一个位置走一步过来的，这一步可能是从上往下走或者从左往右走。
所以到达这个位置的可能性总数，就是到达这两个前置位置的可能性总数之和。
由于每次计算只涉及到前一个状态，可以干掉一个维度。
涉及到二维状态转移，需要 $O(mn)$ 这个水平的时间。

值得一提的是，这题交换行列并不影响结果。通过把相对较小的那个维度顾定成 $m$，可以进一步降低两种方法的理论时间或空间复杂度。
实际上并没有数量级上的提升，但是调用自身的写法很有意思，有必要积累一下。

具体实现

组合公式

class Solution {
    public int uniquePaths(int m, int n) {
        // 通过调用自身来固定 m
        if (m > n) {
            return uniquePaths(n, m);
        }
        long res = 1;
        for (int i = n, j = 1; j < m; i++, j++) {
            res = res * i / j;
        }
        return (int) res;
    }
}

动态规划

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

空间优化

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}