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