Dynamic Programming is an algorithmic paradigm in which a problem is solved by identifying a collection of subproblems and tackling them one by one, using the results from previous problems to help solve the current one, until they are all solved.

If you are familiar with Divide and Conquer algorithms, the idea of dividing a problem into subproblems may sound familiar. The key difference is that in Divide and Conquer, you can solve each subproblem individually, in a more isolated fashion (hence the "Divide" in "Divide and Conquer"). In Dynamic Programming however, you use the results of the previous subproblems to help you solve the current one.

Example: Fibonacci Numbers

The Fibonacci Sequence is a famous series of numbers where each number is the sum of the two preceding ones. Mathematically, it is defined as:

$$F(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F(n-1) + F(n-2) & \text{if } n > 1 \end{cases}$$

The first couple Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13... and so on.

Now let's work together to come up with an algorithm that prints the nth Fibonacci number.

Approach 1: Divide and Conquer❌

You'll notice that since we have a recurrence relation defined for Fibonacci numbers, maybe it would be a good idea to write a Divide and Conquer algorithm that uses recursion. So let's do that:

function fibonacci(n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Alright, so here we used a recursive function for our divide and conquer algorithm. To calculate the nth Fib number, we calculate and add the (n-1)th and (n-2)th Fib numbers.

Now, what's the runtime complexity of this algorithm?

• At each recursive call, the algorithm branches into two recursive calls, each with an input that's one less than the previous one

• Each recursive call involves calculating the Fibonacci number of the previous two numbers until reaching the base case

This means that our algorithm has a runtime complexity of O(2^n), not very good! 😞

You'll notice a glaring inefficiency in this approach. Let's say we call our function to find the 4th Fib number. Our algorithm will:

• Calculate the 4th Fib number by:

  • Calculating the 3rd Fib number by:

    • Calculating the 2nd Fib number by:

      • Calculating the 1st Fib number (1)

      • Calculating the 0th Fib number (0)

    • Calculating the 1st Fib number (1)

  • Calculating the 2nd Fib number by:

    • Calculating the 1st Fib number (1)

    • Calculating the 0th Fib number (0)

The problem is that we're re-calculating the same Fibonacci numbers over and over again. If we've already calculated, say, the 2nd Fibonacci number, it would be inefficient to calculate it again later on in the runtime.

If only there was a way to fix this problem with an algorithmic paradigm in which we can leverage the results from the previous subproblems while solving the current one...🤔

DP to the rescue!

Approach 2: Dynamic Programming✔️

Now let's revise our algorithm using DP instead.

function fibonacci(n) {
    let fib = new Array(n + 1);

    fib[0] = 0;
    fib[1] = 1;

    for (let i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib[n];
}

Let's compare this to the DC algorithm from earlier. Not only is this code easier to trace (recursive functions can be tough!), you can see that the runtime complexity of this algorithm is O(n), much better! (There are still better ways to do this problem to optimize space, but I don't want to get into it now)

As you can see, since our subproblems depended on the results of previous subproblems, the dynamic programming paradigm beats divide and conquer as a solution.

6 Steps for Implementing Dynamic Programming

When planning out your DP algorithms, these are the main steps you can follow:

1. Defining the subproblems, and corresponding array/structure to store the results.

2. Define the base cases.

3. Define the recursion for your subproblems (or perform case analysis). How will each subproblem be determined, given the results of the previous subproblems?

4. Which way will you order the subproblems (increasing/decreasing)?

5. What is the final output of your algorithm (the last index of the array, maybe)?

6. Put it all together to create your algorithm!

In our Fibonacci example:

1. The subproblems were each of the Fibonacci numbers from 0,...,n. fib[] was our array for storing the results.

2. The base cases are fib[0] = 0 and fib[1] = 1, just like the actual base cases of the Fibonacci sequence.

3. The recursion was fib[i] = fib[i - 1] + fib[i - 2]

4. We solved the subproblems in increasing order, since each subproblem depended on the subproblems before it.

5. The final output is fib[n]

Optimizing Space

Looking back at the Fibonacci algorithm, there's a method we can use to optimize it to save some space.

If you think about it, each subproblem only depends on the two before it. Knowing this, it doesn't make sense to have fib[4] or fib[10] still in memory when we're solving fib[220], for example. Thus, instead of storing all of the subproblems in an array, we can just keep track of the results from the two previous subproblems. Here's a look at how this works:

function fib2(n) {
    let a = 0 // Prev 2
    let b = 1 // Prev 1
    let c; // Temp variable for swapping
    if (n == 0) return a; // Base case

    for(let i = 2; i <= n; i++) {
        c = a + b; // c is temp variable for swapping
        a = b; 
        b = c; 
    }

    return b;
}

Now, we're only storing results for the two previous subproblems at a time. So now we've gone from O(n) space complexity to O(1). Nice!

When implementing a dynamic programming algorithm, it's important to know exactly what each subproblem depends on so you can choose an efficient method to store the results of your subproblems.

Example 2: Electric Car⚡

Let's try a bit of a harder question than the Fibonacci example.

Suppose you have an electric car that runs on a battery. A battery with charge C can take you C miles down the road. There are battery stations at each mile marker down a long straight road where you can swap your battery with the battery they have available. The data is given in the form of a list of battery charges [C_0, C_1,..., C_n], where C_0 is the initial charge of your battery at mile marker 0, and each other C_i is the charge of the battery at mile marker i.

You are also given the price of each battery, [P_0,..., P_n], the price of each battery at each mile marker. (Note that P_0 is free)

Our goal is to design an algorithm to calculate the minimum cost to get to the end.

Alright, let's design the algorithm using the steps above:

1. Define the subproblems: Define A[k] to be the minimum cost to get from mile marker k to mile marker n + 1, given that you buy a battery at mile markerk.

2. Base Cases: The base case occurs when k = n. In this case, A[n] is equal to P_n

3. Recursion: The minimum cost at each subproblem, A[k] is:

$$A[k]=min(P_k+A[i])$$

For all i such that

$$k < i \le min(k+C_k, n)$$

Basically, A[k], the solution for the current subproblem, is going to be the minimum of the A[i]'s, where i is greater than k, but less than n (the last mile marker), or k + C_k (the last mile marker we can get to if we buy a battery at marker k).

For example, let's say we want to buy a battery at mile marker 7, and it will give us 3 charge. That means that A[7] is going to be the minimum between A[8], A[9], and A[10] (assuming there are at least 10 markers). Anything higher and we won't be able to get to them!

1. Ordering of the subproblems: You'll notice that this time, the current subproblem depends on the ones greater than it, so we are going to order our subproblems in decreasing order.

2. Output: Our final output will be A[0].

So that's the basic idea behind the algorithm for this problem. I'm going to leave the actual implementation of this algorithm as an exercise. Additionally, is it possible to optimize space in this algorithm like we did for the Fibonacci example? Why or why not?

Two Dimensional Dynamic Programming

Sometimes, when you're solving subproblems that are a bit more complex, you'll need more than just a single array to store the results of your subproblems. This is where Two-dimensional dynamic programming comes in, where intermediate results of subproblems are stored in a table (or 2D array).

The procedure for implementing 2D-DP is similar to 1D-DP. Let's take a look at an example.

2-DP Example: Froggy!🐸

You are a frog and you start on the upper left corner of a nxn square pond. There is a lily pad on every lattice point of the pond. Each lily pad has a bounciness where you can bounce exactly the amount of distance from that lily pad directly to the right or directly down.

The bounciness is given to you as an array where A[1, 1] is the bounciness of the lily pad in the top-left corner and A[n, n] is the bounciness of the lily pad in the bottom right corner.

Determine if it is possible to reach the bottom-right lily pad from the top-left lily pad.

1. Subproblems: Define B[i, j] to be TRUE if you can reach the (i, j) lily pad within the constraints, and FALSE otherwise.

2. Base Cases: B[1, 1] = TRUE, since you start there.

3. Recursion: You can reach lily pad (i, j) from a lily above, or from a lily to the left. So we iterate through all of the cells directly above and to the left, and B[i, j] is TRUE if any of them return true. So we have:

   • B[i, j] = OR(B[i', j']), where:

     • 1 ≤ j' < j (any lily to the left) and j - j' = A[i, j'] (you can legally bounce from that lily to the current one)

     • 1 ≤ i' < i (any lily from above) and i - i' = A[i', j] (you can legally bounce from that lily to the current one)

4. Ordering: Since you can only travel to the right or down, we must iterate in increasing order. We can iterate by the rows and then the columns, or the columns and then the rows, as long as it is in increasing order.

5. Output: We will return B[n, n]

I'll leave the actual implementation of the algorithm up to the reader again.

Bonus 2-DP Example: Coins🪙

You are given coins with values D_1, D_2,..., D_n, as well as a target price, P. Create an algorithm that returns the smallest number of coins you can use from the list to make exactly P cents, or return infinity if it is not possible. You can use each coin at most once.

For example, if we have the coins [1, 3, 2, 4] with a target 6, our algorithm should return 2, since it will use the coins with the values 2 and 4.

1. Subproblems: We will let B[i, j] be the smallest number of coins you can use from coins 1,...i to make the value j.

2. Base cases: Our base cases are B[i, 0] = 0 for all i's, and B[0, j] = Infinity, for all j's greater than 0. No coins are needed to make 0 cents, and there's no way to make j cents with 0 coins.

3. Case Analysis: We perform case analysis based on if we want to include the current coin or not.

   1. Case 1: Include the new coin

      • Let v be the value of the coin, coin i. Note that if v > j, then we cannot choose this case.

      • This means that B[i, j]= 1 + B[i - 1,j - v]

      • Note that if B[i - 1,j - v] is infinity, then B[i, j] will be, too.

   2. Case 2: Don't include the new coin

      • If we choose not to include the new coin, i, then B[i, j]=B[i - 1,j]

   3. Now, do determine whether or not to include/exclude the current coin (which of the two cases), we take the minimum of the two cases:

$$B[i,j]=min(1+B[i-1,j-v], B[i-1,j])$$

1. Ordering of Subproblems: Calculating B[i, j] depends on the cells in the table before it, so we solve the subproblems in increasing order

2. Final Output: We will return B[n, P]. If it is infinity, then it is impossible.

3. Runtime: The runtime of this algorithm is O(nP). We loop through the number of coins, n, and there is an inner loop iterating through the prices 1,...,P. All other operations are constant, so our runtime is O(nP).

Here is what this algorithm looks like in JavaScript:

function minCoins(coins, P) {
    const n = coins.length;

    // Create a 2D array
    const B = new Array(n + 1).fill(null).map(() => new Array(P + 1).fill(Infinity));

    // Base cases
    for (let i = 0; i <= n; i++) {
        B[i][0] = 0; // No coins needed to make value 0
    }
    for (let j = 1; j <= P; j++) {
        B[0][j] = Infinity; // Cannot make value j without any coins!
    }

    // Fill the table
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= P; j++) {
            const v = coins[i - 1]; // Value of the current coin
            if (v <= j) {
                B[i][j] = Math.min(1 + B[i - 1][j - v], B[i - 1][j]);
            } else {
                B[i][j] = B[i - 1][j];
            }
        }
    }

    return B[n][P];
}

Let's run the algorithm with the following setup:

const coins = [1, 3, 2, 4];
const target = 6;
console.log(minCoins(coins, target));

Running this, as expected, give us the answer 2. This solution uses the coins with values 2 and 4. Note that our algorithm is not concerned with which coins it is chooses to get this answer, only with how many.

Now, this problem may be a bit harder to trace than the Froggy example. So let's take a look the table of solutions for each subproblem:

Conclusion

Thanks for reading! This is my first ever blog post, so if you liked it, then maybe follow?

Note: The last three example problems are taken from my UCSD CSE 101 class, but the solutions and explanations are my own!