A Step by Step Guide to Dynamic Programming

Dynamic programming is a nightmare for a lot of people. Although not every technical interview will cover this topic, it’s a very important and useful concept/technique in computer science.

Again, similar to our previous blog posts, I don’t want to waste your time by writing some general and meaningless ideas that are impractical to act on. Instead, the aim of this post is to let you be very clear about the basic strategy and steps to use dynamic programming solving an interview question. And with some additional resources provided in the end, you can definitely be very familiar with this topic and hope to have dynamic programming questions in your interview.

What is dynamic programming?

Before jumping into our guide, it’s very necessary to clarify what is dynamic programming first as I find many people are not clear about this concept. From Wikipedia, dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems. As it said, it’s very important to understand that the core of dynamic programming is breaking down a complex problem into simpler subproblems.

Dynamic programming is very similar to recursion. But when subproblems are solved for multiple times, dynamic programming utilizes memorization techniques (usually a memory table) to store results of subproblems so that same subproblem won’t be solved twice.

Is dynamic programming necessary for code interview?

There’s no stats about how often dynamic programming has been asked, but from our experiences, it’s roughly about ~10-20% of times. So given this high chance, I would strongly recommend people to spend some time and effort on this topic.

Also dynamic programming is a very important concept/technique in computer science. In order to be familiar with it, you need to be very clear about how problems are broken down, how recursion works, how much memory and time the program takes and so on so forth. All of these are essential to be a professional software engineer.

Lastly, it’s not as hard as many people thought (at least for interviews). Of course dynamic programming questions in some code competitions like TopCoder are extremely hard, but they would never be asked in an interview and it’s not necessary to do so. In technical interviews, dynamic programming questions are much more obvious and straightforward, and it’s likely to be solved in short time.

Now let’s take a look at how to solve a dynamic programming question step by step.

Patterns

There’s no point to list a bunch of questions and answers here since there are tons of online. Instead, I always emphasize that we should recognize common patterns for coding questions, which can be re-used to solve all other questions of the same type.

So here I’ll elaborate the common patterns of dynamic programming question and the solution is divided into four steps in general. An example question (coin change) is used throughout this post. You will notice how general this pattern is and you can use the same approach solve other dynamic programming questions.

Coin change question: You are given n types of coin denominations of values V1 < V2 < … < Vn (all integers). Assume v(1) = 1, so you can always make change for any amount of money M. Give an algorithm which gets the minimal number of coins that make change for an amount of money M .

Step 1 –  Problem vs Subproblem

The first step is always to check whether we should use dynamic programming or not. As I said, the only metric for this is to see if the problem can be broken down into simpler subproblems. Fibonacci is a perfect example, in order to calculate F(n) you need to calculate the previous two numbers.

In the coin change problem, it should be hard to have a sense that the problem is similar to Fibonacci to some extent. You can also think in this way: try to identify a subproblem first, and ask yourself does the solution of this subproblem make the whole problem easier to solve? In this problem, it’s natural to see a subproblem might be making changes for a smaller value. If we know the minimal coins needed for all the values smaller than M (1, 2, 3, … M – 1), then the answer for M is just finding the best combination of them. From this perspective, solutions for subproblems are helpful for the bigger problem and it’s worth to try dynamic programming.

Some people may complaint that sometimes it’s not easy to recognize the subproblem relation. I have two advices here. First, try to practice with more dynamic programming questions. Once you’ve finished more than ten questions, I promise that you will realize how obvious the relation is and many times you will directly think about dynamic programming at first glance. Second, try to identify different subproblems. It’s possible that your breaking down is incorrect. In this question, you may also consider solving the problem using n – 1 coins instead of n. It’s like dividing the problem from different perspectives.

Step 2 – Breaking down formula

Now since you’ve recognized that the problem can be divided into simpler subproblems, the next step is to figure out how subproblems can be used to solve the whole problem in detail and use a formula to express it. The formula is really the core of dynamic programming, it serves as a more abstract expression than pseudo code and you won’t be able to implement the correct solution without pinpointing the exact formula.

Let’s take a look at the coin change problem. Suppose F(m) denotes the minimal number of coins needed to make money m, we need to figure out how to denote F(m) using amounts less than m. If we are pretty sure that coin V1 is needed, then F(m) can be expressed as F(m) = F(m – V1) + 1 as we only need to know how many coins needed for m – V1.

Since it’s unclear which one is necessary from V1 to Vn, we have to iterate all of them. So we get the formula like this:

F(m) = min(F(m - Vi)) + 1, for i = 1 ... n

It means we iterate all the solutions for m – Vi and find the minimal of them, which can be used to solve amount m.

Step 3 – Memorization

As we said in the beginning that dynamic programming takes advantage of memorization. Let’s see why it’s necessary. If we just implement the code for the above formula, you’ll notice that in order to calculate F(m), the program will calculate a bunch of subproblems of F(m – Vi). And to calculate F(m – Vi), it further needs to calculate the “sub-subproblem” and so on so forth. The issue is that many subproblems (or sub-subproblems) may be calculated more than once, which is very inefficient.

That’s exactly why memorization is helpful. As the classic tradeoff between time and memory, we can easily store results of those subproblems and the next time when we need to solve it, fetch the result directly. The solution will be faster though requires more memory.

The key is to create an identifier for each subproblem in order to save it. The most obvious one is use the amount of money. We can create an array memory[m + 1] and for subproblem F(m – Vi), we store the result to memory[m – Vi] for future use.

Step 4 – Implementation

I also like to divide the implementation into few small steps so that you can follow exactly the same pattern to solve other questions.

  1. Init memorization. As we said, we should define array memory[m + 1] first.
  2. Check if the problem has been solved from the memory, if so, return the result directly.
  3. Implement the formula.
  4. Save the result to memory.

And here’s the pseudo code:

[code language="cpp"]
// 1. Init memorization.
memory = int[M + 1]
memory[0] = 0

GetMinCount(money) {
  // 2. Check memory.
  if memory.has(money)
    return memory[money]
  
  // 3. Implement formula.
  res = MAX
  for Vi in V1...Vn
    if Vi <= money
      res = min(GetMinCount(money - Vi)) + 1

  // 4. Save to memory.
  memory[money] = res
  return res
}
[/code]

Bottom-up (optional)

Some people may know that dynamic programming normally can be implemented in two ways. The one we illustrated above is the top-down approach as we solve the problem by breaking down into subproblems recursively. A reverse approach is from bottom-up, which usually won’t require recursion but starts from the subproblems first and eventually approach to the bigger problem step by step.

Usually bottom-up solution requires less code but is much harder to implement. For interviews, bottom-up approach is way enough and that’s why I mark this section as optional.

Conclusion

I hope after reading this post, you will be able to recognize some patterns of dynamic programming and be more confident about it. In fact, we always encourage people to summarize patterns when preparing an interview since there are countless questions, but patterns can help you solve all of them.

There are also several recommended resources for this topic:

Don’t freak out about dynamic programming, especially after you read this post. Let me know what you think 🙂

The post is written by Gainlo - a platform that allows you to have mock interviews with employees from Google, Amazon etc..

I'd like to learn more

Share on Facebook8Tweet about this on TwitterShare on LinkedIn1Share on Reddit0

4 thoughts on “A Step by Step Guide to Dynamic Programming

  1. It seems that this algorithm was more forced into utilizing memory when it doesn’t actually need to do that. The solution I’ve come up with runs in O(M log n) or Omega(1) without any memory overhead. Here’s how I did it.

    M = Total money for which we need to find coins
    Vn = Last coin value
    1. Check if Vn is equal to M. Return it if it is. If it’s less, subtract it from M. If it’s greater than M, go to step 2. (Saves time)
    2. Run binary search to find the largest coin that’s less than or equal to M. Save its offset, and never allow binary search to go past it in the future. Subtract the coin value from the value of M. [Now M’]

    Those two steps are the subproblem. Run them repeatedly until M=0. Have an outer function use a counter variable to keep track of how many times we’ve looped through the subproblem, and that answers the original question. (Find the minimum number of coins needed to make M.)

Leave a Reply

Your email address will not be published. Required fields are marked *