algorithm - 生成二项式系数的最快方法

Question

我需要计算一个数字的组合。

当 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 的最有效方法是什么？？

Answer 1

您可以使用动态规划来生成二项式系数

您可以创建一个数组，然后使用 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 的最大值