组合数 C(n, k)表示从 n 个元素中选择 k 个元素的组合数，其公式为：

$$
C(n, k) = \frac{n!}{k!(n-k)!}\tag{1}
$$

其中”!”表示阶乘，即 $n! = n * (n-1) * (n-2) * … * 1$。

然而，直接使用这个公式编写代码计算组合数可能会导致溢出，因为阶乘的值增长非常快。因此，我们通常使用更有效的方法来计算组合数。

k 分数分解

我们可以通过变换公式 (1) 得到一个新的适合程序运算的公式，计算过程如下：

$$
C(n, k) = \frac{n!}{k!(n-k)!} \
= (\frac{1}{1} * \frac{1}{2} * \frac{1}{3} * … * \frac{1}{k}) * \frac{n!}{(n-k)!}
$$

展开 $\frac{n!}{(n-k)!}$ 得到：

$$
C(n, k) = (\frac{1}{1} * \frac{1}{2} * \frac{1}{3} * … * \frac{1}{k}) * [(n-k+1) * (n-k+2) * … * n] \
= \frac{(n-k+1)}{1} * \frac{(n-k+2)}{2} * … * \frac{n}{k}\tag{2}
$$

也就是说，我们得到了一个等价的组合数公式 (2) ，通过这个公式，我们能很容易写出一段代码实现组合数的计算：

public class Main {
    public static long combinationByK(int n, int k) {
        long res = 1;
        for (int i = 1; i <= k; i++) {
            res = res * (n - k + i) / i;
        }
        return res;
    }
}

这个函数的时间复杂度是 O(k)，空间复杂度是 O(1)。

递推公式

组合数的递推公式是：

$$
C(n, k) = C(n-1, k-1) + C(n-1, k)\tag{3}
$$

这个公式的含义是，从 n 个元素中选择 k 个元素的组合数等于从 n-1 个元素中选择 k-1 个元素的组合数（即选择了特定的一个元素）和从 n-1 个元素中选择 k 个元素的组合数（即没有选择特定的那个元素）的和。

我们很容易直观得想到通过递归的方法实现它：

public class Main {
    public static long combinationByDP(int n, int k) {
        if (k == 0 || k == n) {
            return 1;
        }
        return combination(n - 1, k - 1) + combination(n - 1, k);
    }
}

然而，这个函数的时间复杂度是 O(2^k)，空间复杂度是 O(k)，效率非常低。因此，我们通常通过动态规划的方法实现这个组合数公式：

public class Main {
    public static long combinationByDP(int n, int k) {
        long[][] dp = new long[n + 1][k + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
        return dp[n][k];
    }
}

这个函数的时间复杂度是 O(nk)，空间复杂度也是 O(nk)，因为我们需要计算并存储所有小于或等于 n 和 k 的组合数。

相比k 分数分解的方法，这个程序的缺点是它需要更多的时间和空间。因为它需要计算并存储所有小于或等于 n 和 k 的组合数，而不仅仅是 C(n, k)。如果 n 和 k 都非常大，这可能会成为一个问题。然而，如果我们需要计算很多不同的组合数，这个程序可能会更快，因为它可以复用已经计算过的组合数。

应用：解决矩阵最大对角路径问题

给定一个 m * n 的矩阵，求从左上角到右下角的最大对角路径的和。对角路径是指从左上角到右下角的路径， 每一步只能向右或向下移动 。

问题分析

这是一个经典组合数问题。我们可以这样抽象这个问题：假设我们有一个 m * n 的矩阵，我们要从左上角走到右下角，每次只能向右或向下移动。那么，从左上角到右下角的任何路径都必须包含 m - 1 步向下移动和 n - 1 步向右移动，总共 m + n - 2 步。

问题就转化为了在 m + n - 2 步中选择 m - 1 步向下移动的方式有多少种，这就是一个组合问题。答案是 $C(m+n-2, m-1)$ 或 $C(m+n-2, n-1)$ ，其中 $C(a, b)$ 表示从 a 个元素中选择 b 个元素的组合数。

通过 k 分数分解计算组合数

根据前文的式 (2) ，我们可以得到以下代码：

public class Main {
    public static void main(String[] args) {
        // 测试：3 * 7 的矩阵
        System.out.println(uniquePaths(3, 7));
    }

    public static long uniquePaths(int m, int n) {
        int a = m + n - 2;
        int b = Math.min(m - 1, n - 1);
        long res = 1;
        for (int i = 1; i <= b; i++) {
            res = res * (a - b + i) / i;
        }
        return res;
    }
}

这个函数的时间复杂度是 O(min(m, n))，空间复杂度是 O(1)。

通过动态规划计算组合数

我们也可以通过动态规划的方法计算组合数。

我们可以定义一个二维数组 dp，其中 dp[i][j] 表示从左上角到位置 (i, j) 的路径数量。对于位置 (i, j) ，我们只能从位置 (i-1, j) 或位置 (i, j-1) 到达，所以 dp[i][j] = dp[i-1][j] + dp[i][j-1] ：

public class Main {
    public static void main(String[] args) {
        // 测试：3 * 7 的矩阵
        System.out.println(uniquePaths(3, 7));
    }

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