Dynamic Programming

Solving that classic fibonacci problem…

If you’re like me and new to the world of Algorithmic problem solving, you might find yourself a bit overwhelmed to say the least. I recommend investing the time to watch Alvin Zablan’s lecture on tackling these types of problems. The lecture focuses more on learning how how to find strategies or “learning how to learn”, rather than memorizing the correct solution.

This blog will cover the first solution from this lecture. The Fibonacci problem.

Fibonacci

If you’re also like me and not a mathematician, all you need to know about the Fibonacci sequence is that it is a list of numbers where the first and second index of the string equals the third index. For example:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34….

0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3 … ect

The Problem

In this case, we want to create an algorithm that can find the 100th Fibonacci number.

Step 1. — Establish a base case.

The first thing we want to do is figure out when we want our function to “break” or stop running. With the Fibonacci sequence, if we hand any number that’s less than or equal to 2, we know that value will be 1.

def fib(n):
    if (n <= 2):
        return 1

Step 2. — Establish a “brute force” solution.

Here we’re going to call this function internally with number provided. We want to subtract 1 from the given number than add that to the result of the function being called again with 2 being subtracted. This gives us the first index being added to the second index. (1 + 2 = 3 for example)

def fib(n):
    if (n <= 2):
        return 1
    return fib(n - 1) + fib(n - 2)

If we call this function with “3” for N, we’ll get 2, which is correct as 2 is the third index in the sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34….

However, if we try calling this function with 100, something bad happens: our application freezes.

So why does this happen? It’s because every time our function iterates, it has to call itself, which means it has to iterate again, which means repeating the same work it just completed. Imagine reading a book and the only way to read the next word is by re-reading every word that came before it again. You wouldn’t make it past the first page.

def fib(n):
    print(n)
    if (n <= 2):
        return 1
    return fib(n - 1) + fib(n - 2)

print(fib(100))

Step 3. — Memoization

So how do we solve for this and make this solution viable? We need a way for the computer to ‘remember’ all of the work it’s already completed. We can accomplish this by using a dictionary. (Or object in Javascript, or Hash in Ruby)

If we create a key/value pair in an object that stores the value of the calculations we’ve already completed, we can skip this work in the next iteration and move on. (We remember the words we’ve already read) The key here is that we need to hand this dictionary back in every iteration so that the algorithm can continue to expand it with each new iteration:

def fib(n, memo = {}):
    if n in memo:
        return memo[n]
    if (n <= 2):
        return 1
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(100))

Now when we execute, we get a result in seconds. The 100th Fib number is 354224848179261915075