Algorithms for Coding Interviews in Python/

...

/

Memoizing Fibonacci Numbers

Memoizing Fibonacci Numbers

In this lesson, we are going to reduce the time complexity of the Fibonacci code we wrote using a dynamic programming technique called memoization.

We'll cover the following...

Let’s memoize the code now and see where that leads us. The basic idea is to check if a list already contains the result of the Fibonacci number that we are trying to find before calculating it.

Memoized code

Have a look at the complete code in Python:

Python 3.5
def fib(num, lookup_table):
  """
  Finds nth fibonacci number
  :param num: An integer number
  :param lookup_table: Stores already calculated fibonacci number
  :return: nth fibonacci number
  """
  if lookup_table[num] == -1: # Check if already present
    
    # Adding entry to table when not present
    if num <= 1:
      lookup_table[num] = num
    else:
      lookup_table[num] = fib(num - 1, lookup_table) + fib(num - 2, lookup_table)
  return lookup_table[num]
# Driver code to test above function
if __name__ == '__main__':
  num = 6  # Finding the nth Fibonacci number 
  lookup_table = [-1] * (num + 1)  # Initializing the lookup table to have -1 of size num + 1
  print(fib(num, lookup_table))

The function is very simple. It takes as input:

  • the number n which represents the Fibonacci number that we want to find— which is 66 in our case.
  • A lookup table
...