Algorithms for Coding Interviews in C++/

...

/

Tabulating Fibonacci Numbers

Tabulating Fibonacci Numbers

Let's tabulate the code to find the nth Fibonacci number now.

We'll cover the following...

Lets find the nthnth Fibonacci number using bottom-up tabulation. This approach uses iteration and can essentially be thought of as recursion in reverse.

Pseudocode

Initialize look up table of length n+1
Set first two values to 0 and 1
For i = 2 till n-1:
  lookuptable = lookuptable[i-1] + lookuptable[i-2]
return lookuptable[n];

Tabulated Version #1

Have a look at the tabulated code in C++,

Press + to interact
#include <iostream>
using namespace std;
int fib(int const n, int lookupTable[]) { 
  lookupTable[0] = 1; // Set zeroth and first values
  lookupTable[1] = 1;
  
  for (int i = 2; i <= n; i++) 
      lookupTable[i] = lookupTable[i-1] + lookupTable[i-2]; // Fill up the table by summing up previous two values
  
  return lookupTable[n-1]; // Return the nth Fibonacci number
} 
int main() {
  const int n = 6;
  int lookupTable[n+1];
  cout << fib(n, lookupTable) << endl;
}

This algorithm,

  • Initializes a
...