In the context of algorithms, dynamic programming is a technique for solving a certain type of problem by breaking it into subproblems, solving those subproblems, and using the results to find the solution to the original problem.
The purpose of this tip isn’t to explain how dynamic programming works. There are already more than enough free online resources for that purpose. Here are a few:
- A short TopCoder tutorial: Dynamic Programming: From Novice to Advanced
- Another short tutorial on Brilliant: Dynamic Programming
- If you really like math: Dynamic Programming, Chapter 11 from the textbook Applied Mathematical Programming by Bradley, Hax, and Magnanti.
- If you prefer video tutorials: Dynamic Programming by Tushar Roy (Coding Made Simple) on YouTube.
- If you already know the basics and just want sample code: Dynamic Programming Patterns by Atalyk Akash on LeetCode.
The reason I’m bringing up dynamic programming is because, more than any other technique, it illustrates the difference between learning a solution and learning a process to find the solution.
The previous tip has an example of a DP solution pattern that applies to a specific problem type, but isn’t applicable to every DP problem. Although learning specific patterns is a good way to solve certain types of problems quickly, it’s not a viable approach for learning every LeetCode problem type. Instead, we want a process for finding a solution to any DP problem, even when one of our ready-made patterns doesn’t apply.
The rest of this tip assumes that you have some familiarity with Dynamic Programming.
Check if the technique is applicable
One sign you can use DP for a problem is that you can write a function solve(n) and inside that function you can use the result of solve(n-x) for some x. But rather than recalculating solve(n-x) as you would with a purely recursive solution, you store the result and retrieve it when you need it to evaluate solve(n). More formally, we can say that a DP problem has overlapping subproblems and optimal substructure.
Each LeetCode problem type has telltale signs showing which solution method applies. If you learn these signs for each problem type, you’ll have a better chance of knowing which approach to use.
Learn the basic patterns
To calculate solve(n), you could call solve(n-x). Then solve(n-x) could check if the result has already been calculated, and either retrieve it or calculate and store it. Alternatively, you could write a loop that iterates from 0 to n and each iteration could either use a result that has already been calculated or calculate and store the result. For DP, these two approaches are called top-down (using recursion) or bottom-up (using iteration).
Learning a basic algorithmic pattern differs from learning a specific solution, like the DP solution to the House Robber problem. Top-down and bottom-up are basic patterns, meaning every DP solution uses one of them. Similarly, other LeetCode problem types have their own patterns that define the type. For example, every binary search solution has the same fundamental structure, even if the details are different.
Apply a framework
Once you select a pattern, fill in the details using a framework. A framework helps you identify key information in the problem as you’re implementing your solution. For DP, the key information is state, which you can think of as the parameters to your solve function. For solve(n), the state is described by one variable, n. More complicated DP problems require more variables to describe the state.
Each problem type framework has details to look for. For DP, we have state variables. For binary search, we have the the range to search and how to find the midpoint. For graph problems, we have to figure out how to represent the problem data as edges and nodes.
Practice the framework using specific problems
Now we’re back in model problem and model solution territory. To learn a framework, you need to solve problems. But when you approach problems from the more general perspective of a framework rather than a specific solution example, it’s easier to apply what you know to new problems. Dynamic programming is a good place to apply this approach because it’s a flexible technique rather than a specific algorithm. It’s also easy to find tutorials that walk through the process of analyzing DP problems. And when it’s time to practice, LeetCode has plenty of DP problems. Then, once you’re comfortable with dynamic programming, you can apply the pattern/framework approach to other LeetCode problem types.
This year, I’m publishing a series of tips for effective LeetCode practice. To read the tips in order, start with A Project for 2023.