Binary search is an algorithm. It provides step-by-step instructions for efficiently finding a value in a sorted list. A hash table is a data structure. It provides an efficient way to map keys to values. Dynamic programming is an algorithmic technique, or more formally, an algorithmic paradigm. Like divide and conquer, backtracking, or greedy, it refers to a class of algorithms, not a specific algorithm.
Although the term “dynamic programming” doesn’t refer to a specific algorithm, dynamic programming solutions use algorithms and data structures. To solve a LeetCode problem using dynamic programming, you have to write an algorithm to process the input, and you need a data structure to store intermediate results. But the specific algorithm and data structure are not identified for you. This differs from solving a problem tagged as binary search or hash table, where the algorithm or data structure is in the tag. However, dynamic programming problems have some similarities with each other. We will learn about strategies, guidelines, and patterns for solving them.
Dynamic programming (the word programming refers not to coding, but to mathematical optimization) allows us to efficiently solve certain types of problems that can be broken down into subproblems. If you find when solving a problem that you are repeatedly calculating the same value or passing the same parameters to the same function, that’s a sign that dynamic programming may apply. The efficiency of dynamic programming comes from retrieving the results of previous calculations rather than recalculating them.
In technical terms, we say that dynamic programming is a good choice when a problem has these two characteristics:
Overlapping subproblems: When you break the problem into subproblems, you find the same subproblems coming up repeatedly.
Optimal substructure: You can use the optimal solution to the subproblems to find the optimal solution to the overall problem.
Some problems have only overlapping subproblems or only optimal substructure. Dynamic programming is only efficient when a problem has both.
Our goal in studying dynamic programming this year is to learn to solve most Easy and Medium LeetCode problems tagged with that topic. To reach that goal, we will:
Understand the elements of dynamic programming.
Apply that understanding to solve specific LeetCode problems.
Use the model problem/solution approach to select model dynamic programming problems, write model solutions for them, and use spaced repetition to understand and remember what we learn.
Reference: Introduction to Algorithms (CLRS) Chapter 14 covers dynamic programming.
(Image credit: DALL·E 3. The knapsack problem can be solved using dynamic programming.)
For an introduction to this year’s project, see A Project for 2024.