Fibonacci Sequence - Dynamic Programming
Fibonacci Sequence
Fibonacci Sequence: Fn = F(n-1) + F(n-2)
In this note, we will solve this problem using:
- recursion only
- top-down dynamic programming (a.k.a. recursion + memoization)
- bottom-up dynammic programming
Recursion only:
This approach has an exponential runtime complexity and it is too slow. It repeats the same computations again and again. Since this is a recursive approach, we first cover the base cases and then we make recursive calls. Therefore, when trying to compute F300 it would take a great amount of time.
def fibonacci(n):
# Check if input is valid
if type(n) != int:
raise TypeError("n must be a positive integer!")
if n < 1:
raise ValueError("n must be a positive integer!")
# Base cases when n is 0, 1, or 2, the values are 0, 1, and 1.
if n == 0:
return 0
if n <= 2:
return 1
# Recursive calls
return fibonacci(n-1) + fibonacci(n-2)
In order to optimize the recursive case, we can introduce memoization and keep the table of computed values in order to eliminate redundant computations.
Top-Down Dynamic Programming (recursion + memoization)
Eliminating redundant computations results in a significant speedup in execution time.
First, we will implent memoization implicitly, and then we will use a built-in python tool that makes memoization trivial.
#=> declare the dictionary that will store computed fibonacci values
fibonacci_cache = {}
def fibonacci(n):
# Check if input is valid
if type(n) != int:
raise TypeError("n must be a positive integer!")
if n < 1:
raise ValueError("n must be a positive integer!")
# Check if n is already in the fibonacci cache. If so, return it.
if n in fibonacci_cache:
return fibonacci[n]
# Otherwise, we want to:
# COMPUTE the value,
# STORE IT in cache, and
# RETURN it.
# Base cases when n is 0, 1, or 2, the values are 0, 1, and 1.
if n == 0:
value = 0
if n <= 2:
value = 1
elif n > 2:
value = fibonacci(n-1) + fibonacci(n-2)
# Cache the computed value.
fibonacci_cache[n] = value
#return it
return value
To do this in a more clean way, we can use lru_cache
module. LRU Cache stands for Least Recently Used Cache.
#=> Import lru_cache from functools module
from functools import lru_cache
#=> Enter the number of values to cache. Setting it to 1000. By default, python will cache 128 most receantly used values.
@lru_cache(maxsize = 1000)
def fibonacci(n):
# Check if input is valid
if type(n) != int:
raise TypeError("n must be a positive integer!")
if n < 1:
raise ValueError("n must be a positive integer!")
# Base cases when n is 0, 1, or 2, the values are 0, 1, and 1.
if n == 0:
return 0
if n <= 2:
return 1
# Recursive calls
return fibonacci(n-1) + fibonacci(n-2)
Bottom-Up Dynammic Programming
We are able to do this without using recursion in the bottom-up approach.
def fibonacci(n):
# Check if input is valid
if type(n) != int:
raise TypeError("n must be a positive integer!")
if n < 1:
raise ValueError("n must be a positive integer!")
# Base cases when n is 0, 1, or 2, the values are 0, 1, and 1.
if n == 0:
return 0
if n <= 2:
return 1
# Create a table to keep already calcucated values.
table = []
# Insters first 2 trivial values.
table.append(0)
table.append(1)
# Calculate the rest of the values using the previously calculated values.
# Here we go from simpler solutions (bottom) to solving more
# complex solutions (up).
for i in range(2, n+1):
table[i] = table[i-1] + table[i-2]
# Finally return the value that was passed
return table[n]
We can see that this problem is solved the fastest using the bottom-up dynamic programming approach. The run-time is linear.
The Squid