不同路径

发表于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

LeetCode每日一题，922. Sort Array By Parity II

先看题目描述

rComz4.png

大意就是给定一个 m × n 的矩阵，一个机器人只能向右走或向下走，问从左上角走到右下角共有多少条路径

算法和思路

动态规划

我们用 f[i, j] 表示从左上角走到 [i, j] 的路径数量，其中 i 和 j 的范围分别是 [0, m) 和 [0, n)

由于规定机器人只能向右走或向下走，那么机器人走到 [i, j] 经过的前一个格子是 [i -1, j] 或 [i, j - 1]

状态转移方程为：f[i, j] = f[i - 1, j] + f[i, j - 1]，最后返回 f[m - 1, n - 1] 即可

数学组合

这题最开始想到的是用排列组合来做，在一个 m × n 的矩阵里，从左上角走到右下角，一共需要走 m+ n - 2 步，其中要往下走 m - 1 步，往右走 n - 1 步。那么问题就转化成了 m + n - 2 次的总移动里选 m - 1 次往下移动的方案数，就变成了数学中的排列组合问题

组合数如下图所示

rC7crj.png

算法源码

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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];
    }
}

数学组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        if (m > n) {
            return calCum(m + n - 2, n - 1);
        } else {
            return calCum(m + n - 2, m - 1);
        }
    }

    private int calCum(int x, int y) {
        int num1 = 1;
        int num2 = 1;
        for (int i = 0; i < y; i++) {
            num1 *= (x - i);
        }
        for (int i = 2; i <= y; i++) {
            num2 *= i;
        }
        return num1 / num2;
    }
}

下面是题解的实现这个算法的源码，感觉题解的这个代码要更巧妙些

1
2
3
4
5
6
7
8
9
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;
    }
}