C ++中的二项式系数
表示为c(n,k)或ncr的二项式系数定义为（1+X）n的二项式展开式中的xk 系数。
二项式系数还给出了从n个对象中选择k个项的方式数的值，即n个元素集的k个组合。不考虑项目选择的顺序。
在这里，我们给了两个参数n和k，我们必须返回二项式系数nck的值。
示例
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