Learn Dynamic Programming through examples

What is Dynamic Programming?

Imagine the following: You were given several books and was asked to count how many you were given; you would count every single book to figure out the total number. Let’s imagine you were handed seven books. In case you are given one more book, are you going to start counting again all the books that you have? Of course, not. You will add the book given to the total of the books you’ve already counted. Now you have eight books.

This is an example of how we used the information we have already stored in our memory to solve the next problem without having to take the calculations from the start.

The main idea of dynamic programming is to divide a big problem into smaller problems. Once those smaller problems are solved, the results can be stored somewhere in case we need them for later use and then store those partial results of the solved subproblems. This technique of memorizing the results of solved subproblems used later to avoid repeated work is called memoization. Its role is to improve the performance of recursive algorithms by trading space for time.

Think of web browser caching which is great in minimizing network traffic and decreasing page load times. Dynamic programming works in a similar way.

When to solve a problem using Dynamic Programming?

Not all problems can be solved using dynamic programming. The optimization of a problem is possible when a problem has an optimal substructure and overlapping subproblems.

1. Optimal Substructure

A problem has an optimal substructure if an optimal solution can be found for the main problem through finding optimal solutions to its subproblems.

For example: if a node y is right in the shortest path from an origin node x to destination node z, then the shortest path that can be created between x and z is through combining the shortest path from x to y with the shortest path from y to z.

2. Overlapping Subproblems

The term overlapping subproblems refers to finding out if solving a problem requires solving the same problem several times. Dynamic Programming will be used in the case there is a need to use the same subproblems over and over again. If there are no overlapping subproblems, Dynamic Programming is not applicable as there is no use in storing solutions to subproblems if they are never used again.

Top-Down or Bottom-Up

There are two ways of solving dynamic programming problems:

• Top-Down (Memoization) — uses recursion
• Bottom-Up (Tabulation) — uses iteration

Top-Down Approach

Start from the top and break down a problem into multiple subproblems. Imagine that the result of the proposed problem can be defined recursively using the solutions to its many subproblems and these subproblems are overlapping. If that is the case, the results will be stored in the memory (often a table). When attempting to solve another subproblem, check the results in the memory to see if it has been solved before. If not, resolve the subproblem and cache the result.

Example: Fibonacci problem

Fibonacci numbers, usually denoted Fn, is a sequence of numbers, where each number is the sum of the two preceding numbers, starting with 0 or 1.

Fibonacci sequence:

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

OR

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Problem: Write a function to return the nth number in the Fibonacci sequence. Your sequence should start with 1:

The brute solution: we can solve the problem recursively:

It looks like a clear and simple solution. But we have a big problem. There are a lot of repetitive function calls that take time to solve in order to arrive at our solution. In the diagram below, we are repetitively trying to find Fibonacci numbers at indices 0, 1, 2, and 3 on all branches. This is very redundant and requires a lot of work.

Instead, we can use memoization. Let’s solve the same problem using memoization:

Let’s break down the above function:

1. The function fibNumber uses the memo object as a cache to store Fibonacci numbers and their specific indices as keys to find them at a later time when needed.

2. We check to see if the memo has been initialized as an argument when we call the function. If it is needed, we initialize it for usage, otherwise, it is set to an empty object.

3. Then, we should check if we have a cached element for n and return its value it has one.

4. As in the recursive case, we end with checking if n is less than or equal to 1.

5. Finally, we do a recursive call with the value of n while inputting the values we cached of memo into every function, when needed.

Bottom-Up Approach

The base case for this approach is solving the smallest subproblem first. Once solved, use that result to build on and solve bigger subproblems until you solve the entire problem. This is done in a tabular form, which is a table filling algorithm. Let’s take the Fibonacci problem and solve it with iteration which is looping through until a certain condition is met. Just in the case of memoization, the results will be stored for each index but instead of a memo, we will use a table.

We are going to calculate fib(0), then we continue with fib(1) then fib(2), etc. storing the solutions of subproblems bottom-up until we solve the entire problem:

In the above problem, first, we established our base case, then, set our table as an array of the first two numbers as starting points. Then we loop through from the index of 3 until the value of n. Finally, we return the value of n.

Conclusion

Memoization or tabulation?

Choose memoization whenever you don’t need to solve all the problems but want an optimal solution.

Choose tabulation when you need to solve all of the problems as you are going to make many recursive calls.