# 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