Memoization Approach

The idea is to create a lookup table and follow the recursive top-down approach. Before computing any value, we check if it is already in the lookup table. If yes, we return the value. Else we compute the value and store it in the lookup table. Following is the Top-down approach of dynamic programming to finding the value of the Binomial Coefficient.

  • C++

// A Dynamic Programming based

// solution that uses

// table dp[][] to calculate

// the Binomial Coefficient

// A naive recursive approach

// with table C++ implementation

#include <bits/stdc++.h>

using namespace std;

// Returns value of Binomial Coefficient C(n, k)

int binomialCoeffUtil( int n, int k, int ** dp)

{

// If value in lookup table then return

if (dp[n][k] != -1) //

return dp[n][k];

// store value in a table before return

if (k == 0) {

dp[n][k] = 1;

return dp[n][k];

}

// store value in table before return

if (k == n) {

dp[n][k] = 1;

return dp[n][k];

}

// save value in lookup table before return

dp[n][k] = binomialCoeffUtil(n - 1, k - 1, dp) +

binomialCoeffUtil(n - 1, k, dp);

return dp[n][k];

}

int binomialCoeff( int n, int k)

{

int ** dp; // make a temporary lookup table

dp = new int *[n + 1];

// loop to create table dynamically

for ( int i = 0; i < (n + 1); i++) {

dp[i] = new int [k + 1];

}

// nested loop to initialise the table with -1

for ( int i = 0; i < (n + 1); i++) {

for ( int j = 0; j < (k + 1); j++) {

dp[i][j] = -1;

}

}

return binomialCoeffUtil(n, k, dp);

}

/* Driver code*/

int main()

{

int n = 5, k = 2;

cout << "Value of C(" << n << ", " << k << ") is "

<< binomialCoeff(n, k) << endl;

return 0;

}

Output

Value of C(5, 2) is 10

  • JAVA

// A Dynamic Programming based

// solution that uses

// table dp[][] to calculate

// the Binomial Coefficient

// A naive recursive approach

// with table Java implementation

import java.util.*;

class GFG{

// Returns value of Binomial

// Coefficient C(n, k)

static int binomialCoeffUtil( int n, int k,

Vector<Integer> []dp)

{

// If value in lookup table

// then return

if (dp[n].get(k) != - 1 )

return dp[n].get(k);

// store value in a table

// before return

if (k == 0 )

{

dp[n].add(k, 1 );

return dp[n].get(k);

}

// store value in table

// before return

if (k == n)

{

dp[n].add(k, 1 );

return dp[n].get(k);

}

// save value in lookup table

// before return

dp[n].add(k, binomialCoeffUtil(n - 1 ,

k - 1 , dp) +

binomialCoeffUtil(n - 1 ,

k, dp));

return dp[n].get(k);

}

static int binomialCoeff( int n, int k)

{

// Make a temporary lookup table

Vector<Integer> []dp = new Vector[n+ 1 ];

// Loop to create table dynamically

for ( int i = 0 ; i < (n + 1 ); i++)

{

dp[i] = new Vector<Integer>();

for ( int j = 0 ; j <= k; j++)

dp[i].add(- 1 );

}

return binomialCoeffUtil(n, k, dp);

}

// Driver code

public static void main(String[] args)

{

int n = 5 , k = 2 ;

System.out.print( "Value of C(" + n +

", " + k + ") is " +

binomialCoeff(n, k) + "\n" );

}

}

Output

Value of C(5, 2) is 10