62. Unique Paths 「不同路径」

一个机器人站立在 m×n 方格的左上角(下图中标记为“Start”的位置)。

这个机器人只能向右或向下移动。机器人正在试着移动到方格的右下角(下图中标记为“Finish”的位置)。

共有多少条不同的路径可以移动?

上图是 7×3 的方格,共有多少种可能的路径?

提示: mn 最大为 100。

例一:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,共有 3 条路径可以到达右下角:
1. 右->右->下
2. 右->下->右
3. 下->右->右

例二:
输入: m = 7, n = 3
输出: 28

这个题也很有意思,猛的一看很简单,就是一个数理统计问题嘛。

对于这个题,我们当然可以用数学方法去解,这也是大多数人第一次遇到这个问题的想法。同时这个题我们也可以用动态规划来解。

思考一下便可知,从起点到达某一个位置的路径数量,等于 从起点到达其左边的位置的路径数量从起点到达其上边的位置的路径数量 之和。而当这个位置在第一行或第一列时,路径数量为确定的 1,这样我们就可以递归把任意位置的路径数量算出来。

/*
 * 62. Unique Paths
 * https://leetcode.com/problems/unique-paths/
 * https://www.whosneo.com/62-unique-paths/
 */

public class UniquePaths {
    public static void main(String[] args) {
        UniquePaths solution = new UniquePaths();

        System.out.println(solution.uniquePaths(4, 5));
        System.out.println(solution.uniquePaths(5, 5));
        System.out.println(solution.uniquePaths(8, 4));
    }

    private int uniquePaths(int m, int n) {
        if (m == 0 || n == 0)
            return 0;

        // 只能横向或只能纵向移动时,路径只有一种
        if (m == 1 || n == 1)
            return 1;

        int[][] result = new int[m][n];

        // 接下来,其余位置的移动路径的数量等于
        // 其上方位置的路径 与 其左方位置的路径 的和
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0)
                    result[i][j] = 1;
                else
                    result[i][j] = result[i][j - 1] + result[i - 1][j];
            }

        return result[m - 1][n - 1];
    }

    // 仅使用一维数组存储,降低空间复杂度
    private int uniquePaths2(int m, int n) {
        if (m == 0 || n == 0)
            return 0;

        // 只能横向或只能纵向移动时,路径只有一种
        if (m == 1 || n == 1)
            return 1;

        if (m < n) {
            int temp = m;
            m = n;
            n = temp;
        }

        int[] result = new int[n];

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n && j <= i; j++) {
                if (j == 0)
                    result[j] = 1;
                else if (i == j)
                    result[j] = result[j - 1] * 2;
                else
                    result[j] = result[j - 1] + result[j];
            }

        return result[n - 1];
    }
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注