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