Dynamic Programming

Among the many things computer science gets right, naming is not often one of them. I frequently need additional context to pair a name with a concept and dynamic programming is no exception.

The name seems to imply a program that writes itself. Luckily, the concept is much simpler:

Dynamic programming is an approach to solving problems where we cache results to save ourselves future work. In order to be an ideal fit, a given problem must have optimal substructure and overlapping subproblems.

Let’s take a look at a common dynamic programming problem.

The Fibonacci Sequence

First, let’s start off with a naive, brute-force solution which gives us the nth Fibonacci number.

function nthFib(num) {
    if (num === 0) {
        return 0;
    } else if (num === 1) {
        return 1;
    }
​
    return nthFib(num - 1) + nthFib(num - 2);
}

This approach works well for small numbers, but quickly causes problems as our input grows. Even num = 50 produces a noticeable lag.

The solution? You guessed it, dynamic programming. Take a look at this recursive, memoized approach.

function nthFib(num, memoizedResults = []) {
    const memoizedNumber = memoizedResults[num];
    if (memoizedNumber !== undefined) {
        return memoizedNumber;
    }
​
    let calculatedNumber;
    if (num === 0) {
        calculatedNumber = 0;
    } else if (num === 1) {
        calculatedNumber = 1;
    } else {
        calculatedNumber = nthFib(num - 1, memoizedResults) + nthFib(num - 2, memoizedResults);
    }
​
    memoizedResults[num] = calculatedNumber;
    return calculatedNumber;
}

Or if you’re not as comfortable with recursion, here’s how we would approach it from an iterative perspective.

function nthFib(num) {
    const storedAnswers = [0, 1];
    for (let i = 2; i <= num; i++) {
        const oneBefore = storedAnswers[i - 1];
        const twoBefore = storedAnswers[i - 2];
        storedAnswers[i] = oneBefore + twoBefore;
    }
​
    return storedAnswers[num];
}

Now that we’re caching the initial results, large numbers are a breeze. In fact, we’ll bump up against data loss well before we run into performance issues.

Optimal Substructure

As I mentioned earlier, the first thing we need in a dynamic programming problem is optimal substructure.

Optimal substructure indicates that the optimal solution for our current problem can be constructed from the optimal solution to subproblems. nthFib is a great example of this because we construct our optimal solution for nthFib(5) by adding together the optimal solution for nthFib(4) and nthFib(3).

Overlapping Subproblems

The second prerequisite is overlapping subproblems. This implies that we have some sort of repeated work.

Even with a small tree, it’s amazing how much work is unnecessary. Imagine how many nthFib(2) calculations we would have for a problem like nthFib(100).

Here’s what our tree would look like if we could eliminate these repeat calculations.

The reason we’ve eliminated so much of the tree is because we are checking our cache each time to see if some work has already been done. If it has, we simply return the value. If not, as is the case of our first branch, we run the calculation.

This simple change is the difference between an exponential time complexity and a linear time complexity.

Memoization vs. Tabulation

As we saw from the initial examples, we can approach dynamic programming in two ways.

Memoization is a top down approach that typically uses recursion while tabulation is a bottom up approach that relies on iteration.

While both approaches work, there are tradeoffs. Though it’s not always the case, a memoized / recursive solution is usually cleaner. So if time and space complexity are equal, I would generally recommend the memoized approach.

While traditionally more complex, tabulation can offer us space optimizations under specific conditions. Let’s change our initial tabulation example to take advantage of this optimization.

function nthFib(num) {
    const storedAnswers = [0, 1];
    for (let i = 2; i <= num; i++) {
        const oneBeforeCurrent = storedAnswers[1];
        const twoBeforeCurrent = storedAnswers[0];
        const nextFibonacciNumber = oneBeforeCurrent + twoBeforeCurrent;
​
        storedAnswers[0] = oneBeforeCurrent;
        storedAnswers[1] = nextFibonacciNumber;
    }
​
    return storedAnswers.pop();
}

In our updated solution, we’ve maintained linear time complexity and now have constant space complexity. Irrespective of the input, our storedAnswers array will never have more than two items at a time.

While it may not seem like our memoized solution is storing much, we can’t forget about the call stack. The max size of the stack is determined by the depth of our initial branch which will grow linearly with the size of the input.

Additional Resources

A great explanation of tabulation and memoization: https://www.geeksforgeeks.org/tabulation-vs-memoization/

A lot of practice with dynamic programming: https://blog.usejournal.com/top-50-dynamic-programming-practice-problems-4208fed71aa3

Simple explanation for dynamic programming: https://www.quora.com/How-should-I-explain-dynamic-programming-to-a-4-year-old/answer/Jonathan-Paulson?source=post_page—————————