Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
Find Nth Fibonacci Number using Dynamic Programming (Tabulation Approach)
class Solution {
map<int, int> table; // for storing solutions of smaller problems.
int fibonacci(int n) {
for (int i=3; i<=n; i++) { // from smaller to larger problems.
// We go from smaller to larger, so it guarantees that
// values [i-1] and [i-2] exist in the table.
table[i] = table[i-1] + table[i-2];
return table[n]; // actual answer.
int n_th_fibonacci(int n) {
table[1] = 0; // base case that we already know about.
table[2] = 1; // base case that we already know about.
return fibonacci(n); // solve the problem.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment