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

二项式系数 C(n, k)，或组合数，是定义为形如 (1+x) 的二项式 n 次幂展开后 x 的系数（其中 n 为自然数，k 为整数）。C(n, k) 给出了从 n 个物体中随机选出 k 个物体的所有可选组合的数量。例如 C(4, 2) 表示从 4 个物体中随机选出 2 个，一共有 6 种选法，所以 C(4, 2)=6；类似的，C(5, 2)=10。

由二项式的性质有下面的两个公式

C(n, k) = C(n-1, k-1) + C(n-1, k)

C(n, 0) = C(n, n) = 1

现要求 C(n, k) 的具体值是多少。

 

分析：根据上面的两个公式，很容易设计出如下的递归程序进行求解

#include<stdio.h>
 
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
  // Base Cases
  if (k==0 || k==n)
    return 1;
 
  // Recur
  return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
 
int main()
{
    int n = 5, k = 2;
    printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k));
    return 0;
}

但是这种递归算法会反复计算很多子问题很多次，如对于 C(5, 2)，有如下的递归树