Dynamic Programming: Binomial Coefficiet Problem

Problem Statement:

You are given 2 values, n & k. You need to find the binomial coefficient of the values.

Binomial Coefficient is calculated by formula:
C (n,k) = n!/((n-k)! *k!)

Example

3C2

= 3!/((3-2)!*2!)
= 3!/(1! *2!)
= 3!/2!
= 6/2
= 3

Solution

We can solve this problem in 2 ways:

1. Naive Approach
2. DP

1. Naive Approach

In this approach, the value of nCk can be found out by recursively calculating by using below formula:

C(n,k) = C(n-1, k-1) + C(n-1, k)

Note:
C(n, 0) = 1
C(n, n) = 1

The time complexity is O(2^n)

2. DP

As there are many over lapping sub problem, we can solve this by Dynamic Programming.

Here we create temp array to store the values.

For C(5, 2) we get the below tree:

We use bottom up approach to create DP table.
The time complexity is O(n*k)

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <queue>

using namespace std;


int binomial_coeff_using_naive_method(int n, int k)
{
    // Base Cases
    if (k > n)
        return 0;

    if (k == 0 || k == n)
        return 1;
 
    // Recur
    return binomial_coeff_using_naive_method(n - 1, k - 1)
           + binomial_coeff_using_naive_method(n - 1, k);
}
 
int binomial_coeff_using_DP_method(int n, int k)
{
    int C[n + 1][k + 1];
    int i, j;
 

    for (i = 0; i <= n; i++) 
    {
        for (j = 0; j <= min(i, k); j++) 
        {
            if (j == 0 || j == i)
                C[i][j] = 1;
 
            else
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
 
    return C[n][k];
}


int main()
{
    int n = 5, k = 2;
    cout << "Value of C(" << n << ", " << k << ") using naive method is "
         << binomial_coeff_using_naive_method(n, k)<<endl;

    cout << "Value of C(" << n << ", " << k << ") using DP method is "
         << binomial_coeff_using_DP_method(n, k)<<endl;


    return 0;
}

Output:

Value of C(5, 2) using naive method is 10
Value of C(5, 2) using DP method is 10