Dynamic programming is an important algorithmic technique for software engineers to know because it’s useful for solving optimization problems.
Below, we’ll explain exactly what dynamic programming is, how it works, and when and how to implement it. We’ve also included a handy cheat sheet so you can check its space-time complexity at a glance.
Here’s an outline of what we’ll cover:
Let's get into it.
1. Dynamic programming basics
In order to crack questions about dynamic programming, you’ll need to have a strong understanding of the technique, how it works, and when to use it.
1.1 What is dynamic programming?
Dynamic programming is an algorithmic paradigm to create optimal solutions for complex problems by breaking them down into simpler sub-problems that can be solved recursively.
Dynamic programming methods are applicable to problems that have the following two properties:
- Optimal substructure: the optimal solution builds on the optimal solutions of smaller pieces.
- Overlapping sub-problems: the broken-down versions of the problem are repeated.
These properties can be seen when implementing a function to find the nth Fibonacci number. The general implementation is as follows, with n == 0 and n == 1 being the base cases:
The problem has an optimal substructure, because to get the 6th Fibonacci number, the 5th and the 4th Fibonacci numbers must first be found. It also has overlapping sub-problems, because the 4th Fibonacci needs to be found to get both the 5th Fibonacci number and the 6th. In fact, to calculate the 6th Fibonacci number, the 2nd Fibonacci number will be calculated five times, giving this implementation an exponential time complexity. This diagram of a call stack for fib(6) demonstrates the inefficiency of using plain recursion to solve our problem:
Dynamic programming allows us to reduce the complexity of the solution to polynomial time by storing the results of sub-problems for retrieval later.
1.1.1 Use cases for dynamic programming (Java, Python, C++)
Dynamic programming can be applied to common problems like:
- Fibonacci problems
- Finding if a word can be built from a set of strings
- Coin change problem: from a limited set of coins build a specified amount of change
- Min cost path problem: given a matrix of vertex costs or adjacency list of edge costs, find the path with the lowest cost to given vertex
- Assembly line scheduling
- Tile stacking / box stacking problem
- Travelling salesman problem
- Palindrome problems
- Wildcard pattern matching
- Graph coloring problems
- CYK algorithm
- Levenshtein distance
- Diff programs
1.1.2 Example implementation
There are two ways to apply dynamic programming to recursive functions: memoization, the “top-down” approach, and tabulation, the “bottom-up” approach.
Memoization involves storing the solutions to sub-problems in any key-value data structure. The general process of introducing memoization is as follows:
- Add the base inputs to the key-value store.
- Change the base conditions to check if the call’s inputs are in the store, and return the store value if it exists.
- Before returning from the function, store the calculated value in the store. The key is the inputs, and the value is the calculation for the inputs.
This results in the following implementation for our Fibonacci function:
Here, memo is created with the bases of 0 and 1 in the function signature. The base condition is changed to check if n is in memo. If it is, its value will be returned. In addition, the recursive call’s value gets stored in memo. The memo is also passed down the recursive calls – which is important to remember, since it has a default value.
Instead of using recursion to calculate down to the base values, we can use iteration from the base value up to our desired values. This is the principle of tabulation, which pre-computes the solutions to the sub-problems first. The tabulation process works as follows:
- Construct a table to store all the solutions to sub-problems.
- Fill base conditions in the table.
- Use iteration to populate the table.
- Return the table item at n.
For our Fibonacci problem, this yields the following implementation:
First, tab is created to store all the solutions to sub-problems and initialized to all zeros (0). The solution for i will be at index i. The base condition 0 already has value 0, so only the base condition 1 needs to get the value 1. The iteration calculates all the solutions to the sub-problems, but uses the current solution to calculate a future solution. In other words, i = 0 will calculate fib(1) and fib(2) while i = 1 will calculate fib(2) and fib(3). Finally, the solution to the nth sub-problem is returned.
Both memoization and tabulation reduce the time complexity of this Fibonacci function to O(n), while the space complexity remains at O(n). An optimization to the tabular implementation for Fibonacci can have it store only the previous two solutions to sub-problems at a time for a constant space complexity.
1.1.3 How dynamic programming compares to other algorithms
Dynamic programming can be seen as a specialization of divide-and-conquer strategies, since divide-and-conquer requires an optimal substructure (but not overlapping sub-problems). The effect of a dynamic programming solution is usually an improved time-complexity.
Greedy algorithms are also used to solve optimization problems recursively. However, greedy algorithms are not guaranteed to be optimal and can only return a single possible solution. The trade-off is that greedy algorithms are generally faster and more space-efficient than dynamic programming solutions.
Memoization is also used in other contexts to speed up function calls for repeated inputs. These implementations can be in the form of a cache (like a web server cache for incoming requests) or a proxy (like a network proxy for outgoing requests).
2. Dynamic programming cheat sheet
You can download the cheat sheet here.
2.1 Related algorithms and techniques
2.2 Cheat sheet explained
The cheat sheet above is a summary of information you might need to know for an interview, but it’s usually not enough to simply memorize it. Instead, aim to understand each result so that you can give the answer in context.
The cheat sheet is broken into time complexity and space complexity (the processing time and memory requirements for dynamic programming). Dynamic programming is related to several data structures, which are also included in the cheat sheet.
2.2.1 Time complexity
The non-dynamic programming, recursive implementation of Fibonacci has a stack depth of n (the n-1 recursive calls will continue until the base condition of 1 is reached) and a branching factor of 2 – one for fib(n-1) and one for fib(n-2). This gives a total time complexity of O(2^n). Recursive implementations will have a stack depth of m with a branching factor of n to give a time complexity of O(m^n), which is exponential.
The memoization implementation will initialize the memo store the first time it is called with argument n, and the computed value will be extracted from the store the next time it’s called – effectively removing the branching factor. This gives it a time complexity of O(m) only.
The tabulation implementation will only iterate for each sub-problem to also give it a time complexity of O(m). In general, the dynamic programming implementation of an algorithm has a polynomial time complexity.
The longest common subsequence (LCS) problem demonstrates these findings. The LCS problem aims to find the longest subsequence common to two input strings, for example the inputs “csdegf” and “sdbcgafa” have the following subsequence appearing in both: “sdgf.”
A non-dynamic solution to the LCS problem will branch by trimming the first input by one character or trimming the second input by one character until one of the inputs is exhausted, giving a branching factor of 2 and a depth of n, for a time complexity of O(2^n).
A tabulation implementation of the solution has an iteration over the first input (with length i) with a nested interaction over the second input (with length j) giving a time complexity of O(i*j).
2.2.2 Space complexity
The non-dynamic implementation of Fibonacci only uses the stack space for storage. This reaches a maximum depth on the fib(n-1) tree branches, which will have a height of n-1 to give it a space complexity of O(n), which is the general case for recursive functions.
The memoization version of our Fibonacci solution also uses the stack implicitly (for a height of n), and the memo map has a maximum size of n. Our memoization implementation therefore has a total space complexity of O(n).
A tabulation solution only requires the table to store the solutions to sub-problems, which has a size of n. This implementation therefore also has a space complexity of O(n).
As a rule, a dynamic programming solution with n inputs with values of i_1, i_2, …, i_n will have a space complexity of O(i_1 * i_2 * … * i_n).
We can return to our LCS problem to demonstrate these findings too. The non-dynamic programming implementation only uses the stack when comparing input 1 (with length i) and input 2 (with length j), for a stack height of max(i, j) and a space complexity of O(max(i, j)). A tabulation implementation uses a table with dimensions of both i and j to give a O(i * j).
2.2.3 Related algorithms and data structures: hash maps, tree maps, and arrays
The memoization implementation uses a map data structure to store the results of sub-problems. Hash maps are a common key-value data structure that offer constant time insertions and lookups. Some languages have tree maps, which offer log_2 time insertions and lookups, but when both options are available, hash maps are better for memoization. At the end of the memoization implementation, the map will contain n elements to give a space complexity of O(n).
The tabulation implementation uses an array data structure to iteratively solve all the sub-problems. Arrays also offer constant time insertions and lookups. The space complexity for tabulation can vary from constant (when only a constant number of solutions to sub-problems are stored) to linear (when all the solutions to sub-problems are stored).
3. How to prepare for a coding interview
3.1 Refresh your knowledge
Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only dynamic programming but also the rest of the relevant algorithms and data structures. Check out our guides for detailed explanations and useful cheat sheets.
Algorithms explained:
- Depth-first search
- Breadth-first search
- Binary search
- Sorting
- Greedy algorithm
- Backtracking (coming soon)
- Divide and conquer (coming soon)
Data structures explained:
3.2 Practice on your own
Once you’re confident in all of these, you’ll want to start working through lots of coding problems.
Check out the articles in our algorithms questions series for algorithm questions you can practice:
- Depth-first search interview questions
- Breadth-first search interview questions
- Binary search interview questions
- Sorting interview questions
- Dynamic programming interview questions
- Greedy algorithm interview questions
- Backtracking interview questions (coming soon)
- Divide and conquer interview questions (coming soon)
We also recommend working through our list of 73 data structure interview questions. To get used to an interview situation, where you’ll have to code on a whiteboard, we recommend solving the problems on a piece of paper or google doc.
One of the main challenges of coding interviews is that you have to communicate what you are doing as you are doing it. Talking through your solution out loud is therefore very helpful. This may sound strange to do on your own, but it will significantly improve the way you communicate your answers during an interview. Of course, if it’s with someone else playing the role of the interviewer, even better.
3.3 Practice with others
However, sooner or later you’re probably going to want some expert interventions and feedback to really improve your coding interview skills.
That’s why we recommend practicing with ex-interviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.
Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.
Any questions about dynamic programming?
If you have any questions about dynamic programming or coding interviews in general, don't hesitate to ask them in the comments below. All questions are good questions, so go ahead!