If you’re aiming for a top-tier tech job, you have to face the coding interview—and come out on top. And one sure-fire way to impress is to have dynamic programming down pat.
In today’s special guest post, Sam Gavis-Hughson guides us through his formula for solving any dynamic programming problem.
Take it away, Sam!
Disclosure: I’m an affiliate for Sam's courses. While the resources mentioned in this post are free, I may get a small commission if you click the links below and later buy one of his products. Thanks!
When it comes to coding interviews, not all topics are created equal.
Some are relatively easy. For example, even the hardest linked list problems don’t tend to be that difficult because the concept is on the simpler side.
But then there are some topics where even the easiest variations strike fear into the hearts of interviewees everywhere.
One such topic is dynamic programming—an optimization technique programmers can use to speed up our code when we are repeatedly solving the same problem.
Dynamic programming has truly become the defacto hard topic that your interviewer can ask you. If they want to really put you through your paces, that’s what they’ll ask about.
This means that if you’re interviewing for any top tech company, dynamic programming should be at the top of your list of topics to prepare.
What is Dynamic Programming?
Essentially, dynamic programming is a way of making a recursive algorithm more efficient by making sure it doesn’t have to solve the same subproblem twice.
When you use dynamic programming, it stores the results of subproblems so you don’t have to re-compute those results next time they’re needed. It’s an alternative to plain recursion, which requires repeating the solution process every time the subproblem is encountered.
This Stack Overflow answer words it well: “Dynamic programming is when you use past knowledge to make solving a future problem easier.”
Some benefits of dynamic programming are that it saves you coding time, reduces lines of code, and speeds up an algorithm’s processing time.
Now, here’s the crazy thing…
Dynamic Programming Doesn’t Have to Be Hard
The real challenge with dynamic programming is that it is counterintuitive. When you’re trying to solve dynamic programming problems, all the obvious steps that you would normally take actually pull you further away from the correct solution:
- Want to find the optimal solution? You actually need to start with the brute force approach.
- Want to find an iterative solution? You have to start with recursion.
- Want to solve the problem as quickly as possible? You need to slow it down and go step by step.
So if dynamic programming is so counterintuitive, how are we ever supposed to solve these problems effectively?
To start, let’s look at how most people prepare for their coding interviews:
They focus on memorizing solutions.
Rather than being strategic and understanding the underlying techniques, most people focus on simply memorizing as many solutions as they can.
Memorizing gives you a quick and easy win. But the problem is that it ultimately handicaps you.
When you focus on memorizing, your interview prep strategy becomes very simple: just go through as many problems as you can. When you go into an interview, you hope that you see a problem that you’ve studied before.
But this approach quickly leads to diminishing returns. There’s only so much that you can actually memorize, and the number of problems that you could be asked is very large.
Not to mention that this approach prevents you from actually being able to connect the dots.
Imagine learning a new language (let’s say French). You decide that you are going to create a massive deck of flashcards and simply memorize individual words. This is your plan to get to fluency.
So you start memorizing. Here’s one sample set of words:
“suis”, “es”, “est”, “sommes”, “êtez”, “sont”
What is the connection between these words (if you already know French, pretend you don’t for a sec)?
On the surface, it’s not obvious. So if you were just memorizing, you would be memorizing 6 discrete words.
However, there actually is a very close connection between these words: They’re all different conjugations of the verb “to be.”
If we look at the translations, we see:
- “Je suis” – “I am”
- “Tu es” – “You are”
- “Elle est” – “She is”
- “Nous sommes” – “We are”
- “Vous êtez” – “You all are”
- “Ils sont” – “They are”
Notice how much easier this is now that we’ve connected them all in some way that is meaningful to us? Yes we still need to memorize the specifics, but now we can see what connects them.
So what if we could do the same thing with dynamic programming?
Well, it’s never going to happen if we just try to memorize solutions to different problems. The issue is that the similarity between these different problems ISN’T in the solution itself.
The similarity between all dynamic programming problems is in the process.
For the rest of this post, I’m going to show you the exact strategy that you can use to solve any dynamic programming problem, even if you’ve never seen the problem before.
The remainder of this post is excerpted from my free ebook, Dynamic Programming for Interviews, which you can download here.
How to Solve Dynamic Programming Problems Using the Fast Method
What is the most important characteristic of any successful interviewee?
They have a repeatable strategy.
That’s exactly what the FAST Method is. It’s a repeatable strategy for solving any dynamic programming problem, whether you’ve seen the problem before or not.
The FAST Method is an acronym for the 4 steps you need to solve any dynamic programming problem:
- Find the First Solution
- Analyze the First Solution
- Identify the Subproblems
- Turn around the solution
By following these 4 steps, you’ll be able to find the optimal dynamic programming solution for any problem.
Start coding now
Stop waiting and start learning! Get my 10 tips on teaching yourself how to code.
1. Find the First Solution
The first step for any dynamic programming problem (and the step that most people skip) is to find an initial brute-force solution to the problem.
The goal here is to just get something down on paper without any concern for efficiency. To be honest, this should be the first step for any problem you might solve, but it is particularly important for dynamic programming.
There are several keys to think about while doing this step that you’ll want to keep in mind:
- The solution should be recursive. If not, the problem probably isn’t a good candidate for dynamic programming. For a lot more info on effectively coming up with a recursive solution, look here.
- Each recursive call must be self-contained. This means that you cannot store your results to a global variable or pass a results variable into your function. I often refer to the required approach as “building up as you return” and you can learn more about that here.
- It is important that we minimize the number of variables that we are passing into our recursive function. Dynamic programming solutions rely on there being multiple recursive calls with the same input, and the more variables there are, the less the inputs will overlap.
With these basic rules in mind, you will have no trouble using this brute force solution in the FAST Method.
Check out Dynamic Programming for Interviews for detailed walkthroughs of 5 of the most popular dynamic programming problems.
2. Analyze the First Solution
This is the step where we decide whether we can actually use dynamic programming to solve a problem. To do this, we’re going to look at a couple of specific things.
First off, we should be sure to determine what the actual time complexity of our code is currently. One mistake that I see fairly often is attempting to optimize something that doesn’t need to be optimized. If our solution is already efficient, spending a lot of time optimizing is a real waste of time.
With most of our recursive functions, we can use a pretty simple heuristic to compute the runtime. We simply look at the branching factor of our recursive function raised to the depth.
For example, if we were finding all combinations of an input, that would give us a time complexity of `O(2n)`. You can read a lot more about this here.
Next up, if our solution is in fact inefficient (we’re most likely looking for something that is exponential time or worse as being inefficient), we want to see if we can optimize it using dynamic programming.
Dynamic programming actually requires us to meet 2 specific criteria. If we don’t, then it is not possible for us to optimize our problem using dynamic programming. However, if we do, we will likely see a major improvement.
These are the criteria that we need to look for:
Optimal Substructure
The first criterion is that our problem must have optimal substructure. Technically speaking, this means that we must be able to find an optimal solution to a problem by solving for its subproblems. An easier way to think about this is simply that we must be able to solve the problem recursively. If we already found a recursive problem in the previous step, then we can safely assume we have optimal substructure.
Overlapping Subproblems
This is where the actual optimization comes in. If our problem has overlapping subproblems, that means that we are calling the same function with the exact same inputs multiple times. So we’re doing repetitive work for no reason. If we were to cache (or “memoize”) the results, we would be able to save a lot of time.
If we meet these two criteria, then we know that we can optimize our solution using dynamic programming.
Start coding now
Stop waiting and start learning! Get my 10 tips on teaching yourself how to code.
3. Identify the Subproblems
If we find that we are able to use dynamic programming, the next step is to clearly identify the subproblems. Defining the subproblem in plain English is going to make it much easier for us to understand everything that is going on.
To approach this step, we are going to specifically look at our recursive code and see what recursive calls are being made. We then want to define in plain English what the actual meaning of that recursive call is.
For example, if we are computing the nth Fibonacci number, we have 2 recursive calls, fib(n-1) and fib(n-2). To define these in plain English, the function simply returns the nth Fibonacci number. Pretty simple.
Once we’ve identified what the subproblems are, we can also memoize our recursive solution to make it more efficient. All this means is that we are going to add an array or HashMap that stores all of the values that we’ve previously computed.
Each time we make a function call, we will look in our array to see if a result has already been computed for the current inputs. If so, then we can return it without actually computing anything. If not, we compute it and then save it into our array.
For full code and example problems, download Dynamic Programming for Interviews.
4. Turn Around the Solution
If you’ve ever spent any serious time studying dynamic programming solutions in the past, you may have noticed that the vast majority of them are iterative, not recursive. And yet up to this point in the FAST Method, we have only generated recursive solutions.
In this optional final step of the process, we will take our recursive solution and make it into an iterative solution.
When doing dynamic programming, we really have two different options:
- A top-down (memoized) solution
- A bottom-up (tabular) solution
A top-down solution is the recursive solution that we found in the previous step. We call this top-down because we are starting with the goal result that we’re trying to get (ie. fib(5)) and then repeatedly split it into smaller subproblems until we reach our base case.
Bottom-up is simply the opposite of that. Rather than starting with our target input, we start with the base cases. We iteratively compute larger and larger subproblems until we reach our target result.
Both of these approaches will give us the same worst case complexity. However, many people prefer the bottom-up approach because recursive code tends to execute slower than iterative code that does the same work, given that it requires additional overhead.
The key to turning around the solution and finding a bottom-up solution is to look at what the smallest subproblems are. This is why we needed to carefully identify and define the subproblems in the previous step.
We can start with computing our base case. Then we need to determine how to compute a given subproblem, assuming all the smaller subproblems have already been computed. We’ll save all of these subproblem solutions into an array so that we can easily look them up.
See examples of exactly how to do this in my free ebook, Dynamic Programming for Interviews.
At the end of the day, dynamic programming is a challenging topic. It’s not something that you can magically become a master at overnight.
However, it also isn’t something you have to be afraid of. If you nail down your recursion skills and understand the FAST Method, even the most challenging dynamic programming problems can be easily solved during your interview.
Next Steps: Where to Learn More About Dynamic Programming
Want to learn more about dynamic programming? Check out these online courses:
- Intro To Dynamic Programming – Coding Interview Preparation (Udemy): Specifically designed to help you gain foundational knowledge for your software engineering coding interview
- Dynamic Programming – I (Udemy): Also intro-level and geared toward coding interview basics
- Master the Art of Dynamic Programming (Udemy): In-depth theory and practice of dynamic programming
- Learn Dynamic Programming Using Python (Udemy): Hones in specifically on dynamic programming in the Python programming language
- Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming (Coursera): A course offered by Stanford about dynamic programming and other algorithm-related topics
- Dynamic Programming: Applications in Machine Learning and Genomics (edX): Learn about two interesting applications of dynamic programming that meld science and technology, from UC San Diego
About the Author
Sam Gavis-Hughson, founder of Byte by Byte, helps software engineers successfully interview for jobs at top tech companies. He is the author of Dynamic Programming for Interviews, the ebook that shows anyone how to succeed at dynamic programming interviews.