Compute the Binomial Coefficients

EPI 17.4

Description:

Example:

Note

Idea:

C(n, k) = C(n-1, k) + C(n-1, k-1) : for all integer 1 <= k <= n-1
C(n, 0) = C(n, n) : for all n>=0

Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int binomial(int n, int k){
    vector<vector<int>> C(n+1, vector<int>(k+1, 1));
    for(int i=2; i<=n; i++){
        for(int j=1; j<=i-1 && j<=k; j++){
            C[i][j]=C[i-1][j]+C[i-1][j-1];
        }
    }
    return C[n][k];
}

int main(){
    cout<<binomial(2,1)<<endl;
    cout<<binomial(10,5)<<endl;
    cout<<binomial(10,0)<<endl;
}