Last week wrapped up the dynamic programming tutorial for this year. I hope you found it useful. Dynamic programming can be hard to grasp at first compared to other LeetCode topics. But once you internalize the steps to find a top-down solution, you may actually be happy when an interviewer asks you to solve a DP problem instead of something else. If dynamic programming still doesn’t make sense after going through the tutorial, this tip from last year may help you come up with a study plan.

Next, I’ll be doing something a bit different. Normally, I post every week about a project I’m working on. You can find projects from past years on the right side of the page, in the Getting Started section. I have decided to try out a more stealthy approach. Rather than the usual weekly post, I’ll be working on something in the background, so you won’t see new posts for a while. Let see how it goes, and I’ll report back. In the meantime, enjoy the archives, and good luck with your own projects this year.

(Image credit: DALL·E 3)

For an introduction to this year’s project, see A Project for 2024.

Over the past four months, we covered the key ideas in dynamic programming and solved a few practice problems. Let’s review.

« Continue »

Last week, we looked at a dynamic programming counting problem, Climbing Stairs. This week’s problem, LeetCode 91: Decode Ways, is also a counting problem. And although the problems may not seem very similar on the surface, we can adapt the Climbing Stairs solution to solve Decode Ways.

« Continue »

For one subcategory of dynamic programming problems, the goal is to count the number of ways to do something. For example, in LeetCode 62: Unique Paths, we counted the number of ways a robot could move from the start position to the end position in a grid.

This week, we’ll tackle another counting problem, LeetCode 70: Climbing Stairs. It’s an Easy problem whose solution we’ll adapt to solve a Medium problem next week.

« Continue »

Solutions to LeetCode problems of Medium or higher difficulty often require a key insight. Even once you understand the problem and the general technique required to solve it, there’s no way to implement an efficient solution without it. Fortunately, dynamic programming gives us heuristics that we can use to point towards the required idea. For LeetCode 221: Maximal Square, the key insight requires some geometric intuition. But once you figure that part out, the rest of the problem is straightforward.

« Continue »

Earlier this year, we solved LeetCode 53: Maximum Subarray, which asked us to find the sum of the subarray (contiguous non-empty sequence of elements) with the largest sum. This week, we’ll look at a related problem that asks for the largest product.

« Continue »

Many LeetCode problems involve moving around a maze or grid. Mazes tend to be modeled as graphs, but for some problems of this type, dynamic programming is the right approach. We’ll see that in this week’s problem, LeetCode 62: Unique Paths.

« Continue »

LeetCode 416: Partition Equal Subset Sum gives us another chance to practice multidimensional dynamic programming. The problem asks:

Given an integer array nums, return true if you can partition the array into two subsets A and B such that the sum of the elements in A equals the sum of the elements in B. Return false if this is not possible.

« Continue »

LeetCode 1143: Longest Common Subsequence asks:

Given two strings, return the length of their longest common subsequence.

As we saw when solving the Longest Increasing Subsequence problem, a subsequence is formed by selecting elements from the input, with the only restriction being that they remain in their original order. For the LCS problem, if our two input strings are text1 and text2, we can make a common subsequence using these steps: Iterate through text1 in order. For each character, either select it or don’t select it. When we get to the end of text1, we’ll have a subsequence made up of characters from text1. Then iterate through text2 and look for those same characters, in the same order. If we can find them all, we have found a common subsequence. We need to find the longest such subsequence.

« Continue »

As we have seen in previous weeks, a key step in analyzing a dynamic programming problem is selecting state variables that identify the subproblems to be solved. The solutions to these subproblems are stored in a table, which allows us to retrieve them efficiently when they come up again. So far, we have looked at problems with only one state variable. But the dynamic programming process also works when more than one state variable is required.

« Continue »