我需要计算一个数字的组合。
当 n>>p 时计算 nCp 的最快方法是什么?
我需要一种为多项式方程生成二项式系数的快速方法,我需要获取所有项的系数并将其存储在数组中。
(a+b)^n = a^n + nC1 a^(n-1) * b + nC2 a^(n-2) * ............ +nC(n-1) a * b^(n-1) + b^n
计算 nCp 的最有效方法是什么??
最佳答案
您可以使用动态规划来生成二项式系数
您可以创建一个数组,然后使用 O(N^2) 循环来填充它
C[n, k] = C[n-1, k-1] + C[n-1, k];
在哪里
C[1, 1] = C[n, n] = 1
之后,在您的程序中,您只需查看 [n, k] 索引处的二维数组即可获得 C(n, k) 值
更新那样
for (int k = 1; k <= K; k++) C[0][k] = 0;
for (int n = 0; n <= N; n++) C[n][0] = 1;
for (int n = 1; n <= N; n++)
for (int k = 1; k <= K; k++)
C[n][k] = C[n-1][k-1] + C[n-1][k];
其中 N, K - n, k 的最大值
关于algorithm - 生成二项式系数的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11032781/