Over the past four months, we covered the key ideas in dynamic programming and solved a few practice problems. Let’s review.
Concepts
Dynamic programming, unlike most other LeetCode topics, is a process for designing algorithms rather than a single algorithm. That makes DP practice a good way to learn the process of finding solutions, rather than just learning solutions.
If you can express the solution to a problem in terms of the solution to smaller subproblems, you may be able to use dynamic programming to solve it. DP is the right approach if the subproblems overlap, meaning the same subproblems appear repeatedly, and if they have optimal substructure, meaning you can use optimal solutions to subproblems to find an optimal solution to the original problem.
Overlapping subproblems and optimal substructure can seem like abstract concepts, so it helps to look at examples. We started with LeetCode 322: Coin Change. For that problem, we have an input amount and a set of coins. Each subproblem uses a smaller amount, which we calculate by subtracting one coin. The subproblems are overlapping because there are multiple ways to get the same amount using different combinations of coins. The subproblems have optimal substructure because if we know the optimal number of coins to make some amount $x$ and we make a larger amount $x+c$ using exactly one additional coin, then that number of coins is also optimal.
The final characteristic of dynamic programming solutions is the one that makes it time efficient. Since we know we’ll see the same subproblems repeatedly, we can store the result of each subproblem in a data structure the first time we see it, then retrieve it when we see it again. There are two ways to implement this technique: top-down and bottom-up. The top-down approach starts with the original problem and recursively calculates smaller problems until it reaches the base cases. The bottom-up approach starts with the base cases and builds larger solutions until it reaches the original problem.
Sometimes we don’t even need dynamic programming. For certain problems with optimal substructure, we can implement a more efficient solution using a greedy approach. If you discover that your dynamic programming solution only solves each subproblem once, and never returns to it, then there’s no need to store subproblem results. You can instead use an iterative solution that calculates each result in order until it arrives at the original problem. LeetCode 55: Jump Game can be solved using a dynamic programming approach, but there’s a more efficient greedy solution.
After you get some experience solving dynamic programming problems, you’re ready to learn about states and state transitions. A state is a set of parameters that uniquely identifies a subproblem, and a state transition defines how to get from one state to the next. Once you express these two ideas mathematically, it’s often a straightforward process to translate the mathematics into code.
Practice Problems
LeetCode offers a lot of dynamic programming problems, so it’s easy to be overwhelmed with selection. A helpful resource is a curated list like the one at Tech Interview Handbook. All of the dynamic programming problems I used in this tutorial are from that list, including these remaining problems:
LeetCode 53: Maximum Subarray is a well-known problem that attracted attention from researchers for a few decades after it was proposed in the late 1970s. It asks us to find the maximum sum of a subarray. A related problem is finding the maximum product.
LeetCode 300: Longest Increasing Subsequence has a simple DP solution and a more complicated but more efficient solution involving a deck of cards.
We used LeetCode 1143: Longest Common Subsequence and LeetCode 416: Partition Equal Subset Sum to study multidimensional dynamic programming.
LeetCode 221: Maximal Square is a DP problem with a geometric flavor.
For LeetCode 62: Unique Paths, we see how dynamic programming can be used for counting. This problem asks us to count the number of ways for a robot to traverse a grid.
Another counting problem is LeetCode 70: Climbing Stairs, an easy problem that is often used to introduce dynamic programming concepts. We adapted its solution to solve a more challenging counting problem, LeetCode 91: Decode Ways.
Next Steps
This series covered the fundamental concepts of dynamic programming, using a set of practice problems to illustrate how they work. Next time you need to solve a DP problem, you’ll have a process you can use to get started. But as with any LeetCode topic, it takes more than just understanding concepts to solve problems quickly and accurately. I recommend solving the problems from this tutorial more than once over a period of time, and seeking out more problems from LeetCode’s extensive list. For tips on how to structure your practice, see my LeetCode series from last year.
(Image credit: DALL·E 3)
For an introduction to this year’s project, see A Project for 2024.