Learning Dynamic Programming with a popular coding interview question

Alexander Mok
Jun 6 · 6 min read

What is Dynamic Programming?

If you’ve ever heard the term dynamic programming being thrown around and wondered to yourself what that term meant or how to use dynamic programming, this article aims to alleviate those concerns and develop a basic understanding.

A Popular Coding Interview Question

Imagine you are a professional thief and you’ve broken into an art museum. The security will only go off if adjacent paintings are taken off a wall. Given an array of numbers representing the value of each painting determine the maximum value of stolen paintings. In the following array of painting values: [3,5,6,2,1,8], the maximum heist value would be from 3,6,8 for a total of 17. If you would like a moment to try this problem stop reading here, otherwise, the solution is in the following sections.

Setting up the Problem

The first step to solving a problem with dynamic programming is to figure out the overlapping subproblems we are trying to solve. In our case, the subproblems would be which paintings to steal starting from arrays of varying lengths from one to infinity. So if we only had one or two paintings, we would know which one to steal. But if we had three, four, five or more paintings the subproblem is to determine which ones would allow us to walk away with the most value. With these subproblems in hand, we are now going to set up a brute force method to test all possibilities so that we can continue to optimize our solution.

Memoization (Top Down)

Memoization, commonly confused for dynamic programming, simply refers to a technique, we previously mentioned to save a result so that we can use the saved result instead of recalculating it. A top down approach is one that takes a larger problem and breaks it down into smaller subproblems. To put it all together, a top down approach with memoization will start with the whole problem, solve a subproblem once and then save this answer so that if the subproblem comes up again the answer doesn’t need to be recalculated. While this may seem very difficult, our previous, highly inefficient recursive solution is only one minor tweak from being a decent answer to both our thieving algorithm and a top down approach with memoization.

Tabulation (Bottom Up)

Our previous two blocks of code are recursive solutions for our thieving problem, the latter being more efficient than the other. Another approach that deals away with recursion is calculating iteratively (e.g. for loop) from the bottom up, solving the smallest subproblem first then moving to the larger ones. Similar to memoization, tabulation will also store the previous solutions to our subproblems in a table. The main difference lies in how the solution was calculated (recursively vs. iteratively) and how the solution will be used. The bottom up approach with tabulation starts at the smallest subproblem and will build on the previous answer (stored in a table) to eventually reach the answer that we are looking for.

Final Optimized Solution

After working through the problem with all of these different methods we can make one final optimization to the space complexity. We mentioned in our setup that at most we would go two spaces away to check our maximum value, so instead of creating an array to save all of our previous solutions we can save just the previous two.

Conclusion

To summarize the steps to dynamic programming:

DataSeries

A network of data thought leaders, sharing lessons learned, in preparation for the future 🚀

Alexander Mok

Written by

DataSeries

A network of data thought leaders, sharing lessons learned, in preparation for the future 🚀