组合数/二项式系数(Binomial Coefficient)的计算

问题描述

输入: 两个整数 n, m (n >= m >= 0);
输出: 组合数 $\binom{n}{m}$.

解法一: 动态规划(dp)

根据组合数公式 :
$$\binom{n}{m} = \binom{n-1}{m} + \binom{n-1}{m-1}$$
转换为二维递推方程: dp[i][j] = dp[i-1][j] + dp[i-1][j-1]. 注意到当前的第i行的值只依赖于第i-1行,故可以优化为只用一个一维数组。

int compute_binomial(int n, int m) {
    vector<int> dp(m+1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = m; j > 0; ++j)
            dp[j] = dp[j] + dp[j-1];
    return dp[m];        
}
  • 时间复杂度:O(m*n)
  • 空间复杂度:O(n)

Note: 该方法其实计算出了一串组合数序列 $\binom{n}{1}, ..., \binom{n}{m}$, 因此可以直接用于计算二项式展开的所有系数。

解法二: 根据定义直接计算

由组合数的定义:
$$\binom{n}{m} = \frac{n!}{m!(n-m)!} = \frac{n \times (n-1) \times \dots \times (n-m+1)}{1 \times 2 \times \dots \times m}$$
显然简化后的公式比直接计算三个阶乘开销更小,然而需要注意的是乘法溢出的问题。我们希望尽量在计算过程中就约分,而不是分别计算分子分母的乘积。

int compute_binomial(int n, int m) {
    long long res = 1;
    for (int i = 1; i <= m; ++i) {
        res *= n - i + 1;
        // 这里的除法是精确的 assert(res % i == 0);
        res /= i;
    }
    return (int)res;
}

以上的乘法仍有可能导致溢出,即res的范围可能比组合数的大,即使最后结果属于int范围,res的类型也需要long long。但除法一定是能除尽的,为什么呢?因为在第i次循环中,根据定义式我们实际上是在计算$\binom{n}{i}$,这也是为什么乘法是从n开始乘,而不是从n-m+1开始(如果那样则不能保证都能整除)。

  • 时间复杂度:O(m)
  • 空间复杂度:O(1)

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。