Find Binomial Coefficient


// A Dynamic Programming based solution that uses 
// table C[][] to calculate the Binomial Coefficient
#include<bits/stdc++.h>
using namespace std;
 
// Prototype of a utility function that
// returns minimum of two integers
int min(int a, int b);
 
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
    int C[n + 1][k + 1];
    int i, j;
 
    // Caculate value of Binomial Coefficient
    // in bottom up manner
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= min(i, k); j++)
        {
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
 
            // Calculate value using previously
            // stored values
            else
                C[i][j] = C[i - 1][j - 1] +
                          C[i - 1][j];
                          // ncr formula-> (n)c(r)= (n-1)c(r)+(n-1)c(r-1) if r=0,r=n then ncr=1
        }
    }
 
    return C[n][k];
}
 
// A utility function to return 
// minimum of two integers
int min(int a, int b)
{
    return (a < b) ? a : b;
}
 
// Driver Code
int main()
{
    int n = 5, k = 2;
    cout << "Value of C[" << n << "]["
         << k << "] is " << binomialCoeff(n, k);
}
 

Comments

Popular posts from this blog

Linked List 10 operations from which problems are made ( complete guide for you)

Stack - print bracket number