C ++中的二项式系数

表示为c(n,k)或ⁿ c _r的二项式系数定义为（1 + X）ⁿ的二项式展开式中的x ^k 系数。

二项式系数还给出了从n个对象中选择k个项的方式数的值，即n个元素集的k个组合。不考虑项目选择的顺序。

在这里，我们给了两个参数n和k，我们必须返回二项式系数ⁿ c _k的值。

示例

Input : n = 8 and k = 3
Output : 56

这个问题可以有多种解决方案，

通用解决方案

有一种方法可以使用递归调用来计算c(n,k)的值。查找使用递归调用的二项式系数的值的标准公式为-

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

c(n,0)= c(n,n)= 1

使用上述公式的递归调用的实现-

示例

#include <iostream>
using namespace std;
int binomialCoefficients(int n, int k) {
   if (k == 0 || k == n)
   return 1;
   return binomialCoefficients(n - 1, k - 1) + binomialCoefficients(n - 1, k);
}
int main() {
   int n=8 , k=5;
   cout<<"The value of C("<<n<<", "<<k<<") is "<<binomialCoefficients(n, k);
   return 0;
}

输出结果

The value of C(8, 5) is 56

另一个解决方案可能是使用重叠的子问题。因此，我们将使用动态规划算法来避免子问题。

示例

#include <bits/stdc++.h>>
using namespace std;
int binomialCoefficients(int n, int k) {
   int C[k+1];
   memset(C, 0, sizeof(C));
   C[0] = 1;
   for (int i = 1; i <= n; i++) {
      for (int j = min(i, k); j > 0; j--)
         C[j] = C[j] + C[j-1];
   }
   return C[k];
}
int main() {
   int n=8, k=5;
   cout<<"The value of C("<<n<<", "<<k<<") is "<<binomialCoefficients(n,k);
   return 0;
}

输出结果

The value of C(8, 5) is 56