這里函數采用兩個參數n和k，并返回二項式系數 C(n, k) 的值。?

例子：?

輸入： n = 4 和 k = 2

輸出： 6

解釋： 4 C 2 等于 4!/(2!*2!) = 6

輸入： n = 5 和 k = 2

輸出： 10

解釋： 5 C 2 等于 5!/(3!*2!) = 10

????????在本文中，我們討論了 O(n*k) 時間和 O(k) 額外空間算法。C(n, k) 的值可以在 O(k) 時間和 O(1) 額外空間內計算出來。

方法：

1、如果 r 大于 nr，則將 r 更改為 nr，并創建一個變量來存儲答案。

2、從 0 到 r-1 運行循環

3、在每次迭代中更新 ans 為 (ans*(ni))/(i+1)，其中 i 是循環計數器。

4、所以答案將等于 ((n/1)*((n-1)/2)*…*((n-r+1)/r)，等于 nCr。

C(n, k)?
= n! / (nk)! * k!?
= [n * (n-1) *....* 1] / [ ( (nk) * (nk-1) * .... * 1) *?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ( k * (k-1) * .... * 1 ) ]
簡化后，我們得到
C(n, k)?
= [n * (n-1) * .... * (n-k+1)] / [k * (k-1) * .... * 1]

另外，C(n, k) = C(n, nk) ??
// 如果 r > n-r，則 r 可以更改為 n-r

以下實現中利用上述公式計算C(n,k)：

// Program to calculate C(n, k)?
??
#include <bits/stdc++.h>?
using namespace std;?
??
// Returns value of Binomial Coefficient C(n, k)?
int binomialCoeff(int n, int k)?
{?
? ? int res = 1;?
??
? ? // Since C(n, k) = C(n, n-k)?
? ? if (k > n - k)?
? ? ? ? k = n - k;?
??
? ? // Calculate value of?
? ? // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]?
? ? for (int i = 0; i < k; ++i) {?
? ? ? ? res *= (n - i);?
? ? ? ? res /= (i + 1);?
? ? }?
??
? ? return res;?
}?
??
// Driver Code?
int main()?
{?
? ? int n = 8, k = 2;?
? ? cout << "Value of C(" << n << ", " << k << ") is "
? ? ? ? ?<< binomialCoeff(n, k);?
? ? return 0;?
}?
??
// This is code is contributed by rathbhupendra

輸出：
C(8, 2) 的值為 28

復雜度分析：?

時間復雜度： O(r)循環必須從 0 運行到 r。因此，時間復雜度為 O(r)。

輔助空間：O（1），因為不需要額外的空間。