Search⌘ K
AI Features
Home
Courses
Dynamic Programming in Python: Optimizing Programs for Efficiency

The Fibonacci Numbers Algorithm with Memoization

Explore how to optimize the Fibonacci numbers algorithm by applying memoization in Python. Learn to store intermediate results to prevent redundant calculations, significantly improving the algorithm's efficiency and reducing its time complexity from exponential to linear. Understand the benefits of top-down dynamic programming in practical implementations.

We'll cover the following...

Optimizing Fibonacci number’s algorithm

Let’s revisit the Fibonacci numbers algorithm from an earlier lesson of this course.

Python 3.5
def fib(n):
  if n == 0: # base case 1
    return 0
  if n == 1: # base case 2
    return 1
  else: # recursive step
    return fib(n-1) + fib(n-2)
print (fib(10))

We have also reproduced a dry run of Fib(6) below to visualize how this algorithm runs.

Memoization

Now let’s store the results of every evaluated Fibonacci number and reuse it whenever it is needed again. We can use either a list or dictionary for memoization in this problem. In this course, we will use a dictionary because it is ...