Red-Green-Code

Deliberate practice techniques for software developers

  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter

LeetCode Tip 40: Learn Dynamic Programming

By Duncan Smith Oct 11 0

LeetCode 2023

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.

Categories: LeetCode

Prev
Next

Stay in the Know

I'm trying out the latest learning techniques on software development concepts, and writing about what works best. Sound interesting? Subscribe to my free newsletter to keep up to date. Learn More
Unsubscribing is easy, and I'll keep your email address private.

Getting Started

Are you new here? Check out my review posts for a tour of the archives:

  • 2023 in Review: 50 LeetCode Tips
  • 2022 in Review: Content Bots
  • 2021 in Review: Thoughts on Solving Programming Puzzles
  • Lessons from the 2020 LeetCode Monthly Challenges
  • 2019 in Review
  • Competitive Programming Frequently Asked Questions: 2018 In Review
  • What I Learned Working On Time Tortoise in 2017
  • 2016 in Review
  • 2015 in Review
  • 2015 Summer Review

Archives

Recent Posts

  • Do Coding Bots Mean the End of Coding Interviews? December 31, 2024
  • Another Project for 2024 May 8, 2024
  • Dynamic Programming Wrap-Up May 1, 2024
  • LeetCode 91: Decode Ways April 24, 2024
  • LeetCode 70: Climbing Stairs April 17, 2024
  • LeetCode 221: Maximal Square April 10, 2024
  • Using Dynamic Programming for Maximum Product Subarray April 3, 2024
  • LeetCode 62: Unique Paths March 27, 2024
  • LeetCode 416: Partition Equal Subset Sum March 20, 2024
  • LeetCode 1143: Longest Common Subsequence March 13, 2024
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2025 Duncan Smith