Dynamic Programming

Why is creating a memo so hard to grasp.

I recently had a pre-screening technical assessment for a software engineering position. It was divided up into 3 questions. The first two questions I was able to craft in about 45 minutes (with an allotment of 75 minutes to complete the whole thing.). As I reached the final question I felt extremely confident in how my abilities have grown and I was sure I had the third one down in the rest of the time frame. I pulled up the question and after reading the synopsis I knew it was over. I recognized immediately that it was a dynamic programming problem. I’ll spare the details, but safe to say I forgot how you set up the table for a dynamic programming problem and was not able to finish one test by the time the question was over. So, in the spirit of learning and growth. I thought this next blog should be about refreshing myself on dynamic programming concepts.

What is Dynamic Programming?

Dynamic programming at its core. Is the method of caching previous values and using those values again when you recursively (or iteratively) solve the problem. The name comes from a rather interesting story as told by Richard Bellman, of his time at the RAND corporation in the 1950’s:

“An interesting question is, ‘Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he
felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities”

Source: https://pubsonline.informs.org/doi/pdf/10.1287/opre.50.1.48.17791 Pg. 48

Dynamic Programming Example

Explaining the concept is easier with a demonstration. One of the more famous examples of utilizing Dynamic Programming is calculating the nth value of a fibonacci sequence.
The fibonacci sequence is the mathematical concept of starting with the values 0, and 1, and using those values to calculate the next value (e.g. the 3rd number is 0 + 1 = 1, the 4th is 1 + 1 = 2, the 5th is 2 + 1 = 3… etc). This sequence is used to explain the spiral growth of plants and animals in nature (often called the golden ratio).
A simple exercise in coming up with an algorithm may have someone look to a recursive solution. Below is an early example of calculating the nth number in a fibonacci sequence. (All examples will be written in Python3)

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

Great! This algorithm is simple enough to understand, and will give you any value you want.

However…

There is a glaring issue with this algorithm. For trivial numbers, this will be quick enough, but with any higher numbers the run time will be out of control. (Specifically the runtime is close to O(2^n))

Dynamic Programming – Top Down Approach (Memoization)

What could we do about this scenario? If we look at what is being calculated, we see that there are times where we repeatedly calculate the same numbers. Starting at n=5, we calculate n=4 and n=3, then for those we calculate n=3, n=2, n=2, n=1, then n=2, n=1… etc, etc. Why should we calculate the same values over and over again? Could there be a way of remembering those calculations and referencing them?
With the top-down approach to dynamic programming, we create a cache and reference this cache for the succeeding calls (memoization). It is possible now to get a fibonacci call to run in O(n) time with memoization.

def fibonacci(n)
    memo = [0 for x in range(n + 1)]
    fibonacci_helper(n, memo)

def fibonacci_helper(n, memo):
    if n == 0 or n == 1:
        return n
    if memo[n] == 0:
        memo[n] = fibonacci_helper(n-1, memo) + fibonacci_helper(n-2, memo)
    return memo[n]

This code works in three stages. The first stage is we check for our base case 0 or 1. Since they are the base case we just return them in O(1) time. Next is the interesting part. We have an array of n+1 values all set to 0. We use the value of n to correspond to an index, and if the value is 0 (meaning we have not performed any calculations yet) we set that value to the proper calculation. (e.g. memo[2] = 1 + 0), then we pass the memo with the newly cached value back into the helper for further calculations. This in turn helps the final stage where we check for the value at the n index and return it. Giving us our answer. All of this being done in O(n) time with O(n) space. Much better than O(2^n).

Bottom-Up Dynamic Programming

We can also take the approach from the bottom up. Starting with the initial base case values of 0 and 1 and building up from there.

def fibonacci(n):
    if n == 0:
        return 0
    else if n == 1:
        return 1
    memo = [0 for x in range(n)]
    memo[0] = 0
    memo[1] = 1
    for i in range(2, n):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n-1] + memo[n-2]

This will use a for loop to add the correct values to an n-1 size table starting at index 0 = 0 and index 1 = 1. Then to find the value of n, we simply calculate the values from the table at n-1 + n-2. This is done in O(n) time with O(n-1) space.
Of course we can optimize this further. The original question is “What is the nth number of the fibonacci sequence?”. So why should we even keep a table of values when we merely need the answer to the question? A further optimization removes the table in favor of tracking only the necessary values.

def fibonacci(n):
    if n == 0:
        return 0
    a = 0
    b = 1
    for i in range(2, n):
        c = a + b
        a = b
        b = c
    return a + b

Similar to the memo approach, we are building up from 0, 1 to n by saving the values in variables a, b, and a temp variable c. Until we reach just before n, and then return the calculation of a + b for our final answer. This still runs in O(n) time, but we have the added benefit of having O(3) space complexity.

I’m not going to lie. Dynamic Programming is intimidating at first. I feel like you really have to hit your head against a brick wall until you fully grasp it. Then you’ll find those problems that reference Dynamic programming aren’t so bad. As with anything it takes time and practice to get good at this. And because it’s complex to understand at first, it is a favorite interview question style. Hopefully, this sheds a little bit of light on the process.

This blog heavily references “Cracking the Coding Interview – 6th Edition” by Gayle Laakman Mcdowell, chapter 8. The cod is modified into Python3 from the Java examples from the book.