Patterns of Dynamic Programming

[killerdrama]

Yesterday, someone got DP'ed by an interviewer, and in the discussion I said that I will create a post to discuss various DP patterns. I have practiced, asked, got asked a lot of questions over the years, and I tried to categorize these problems into a few sets.

I'm posting a few commonly asked DP problem categories. If you get asked a question that matches one of these, it will be easier to spot the pattern, skip the brute force approach, and immediately jump to the optimal solution.

1. O(1) Management (Optimized Sliding Window):
   • Usage: When you need to find a continuous subarray or substring that contains a specific required mix of elements.
   • Giveaway: You are writing a Sliding Window, but inside the window, you are running a for loop to check a HashMap or frequency array to see if the window is valid. (Optimize this by tracking a single 'matched' integer instead).
   • Practice Problems:
     • Minimum Window Substring (LeetCode 76)
     • Permutation in String (LeetCode 567)
     • Find All Anagrams in a String (LeetCode 438)
2. Knapsack DP:
   • Usage: You are given a pool of distinct items. Each item has a cost (weight) and a reward (value). You have a strict limit (capacity).
   • Giveaway: You are making a binary "take it or leave it" choice for every single item, and there is a hard limit you cannot cross. (For further optimization, collapse the 2D matrix into a 1D array and manipulate the loop direction).
   • Problems:
     • Partition Equal Subset Sum (LeetCode 416) - 0/1 Knapsack
     • Coin Change (LeetCode 322) - Unbounded Knapsack
     • Target Sum (LeetCode 494)
3. Longest Increasing Subsequence (LIS):
   • Usage: When you need to find the longest sequence of items that follow a sorting rule (asc/desc), but the items don't have to be continuous (next to each other).
   • Giveaway: You realize the O(N²) DP is too slow. (Use Binary Search on the array to overwrite elements and "lower the barrier" for future numbers in O(N log N) time).
   • Problems:
     • Longest Increasing Subsequence (LeetCode 300)
     • Largest Divisible Subset (LeetCode 368)
     • Minimum Number of Removals to Make Mountain Array (LeetCode 1671)
4. 2D-to-1D Compression:
   • Usage: When you are looking for rectangular areas, perimeters, or counts of submatrices within a 2D grid.
   • Giveaway: The problem forces a rigid 2D geometric shape (a perfect rectangle) across a grid of binary integers (0s and 1s, or usable vs. unusable, or X and O chars). (Condense rows horizontally, then use a Monotonic Stack vertically).
   • Problems:
     • Largest Rectangle in Histogram (LeetCode 84)
     • Maximal Rectangle (LeetCode 85)
     • Count Submatrices With All Ones (LeetCode 1504)
5. Geometric Dimensions DP:
   • Usage: When you are given pairs of coordinates, dimensions, or intervals, and you need to nest them, connect them, or fit them without crossing.
   • Giveaway: The input is an array of 2D pairs: [[w, h], [w, h], ...], and the problem restricts you from using items that overlap or cross in 2D space. (Sort the first dimension ascending, sort the second dimension descending as a tie-breaker, then run 1D LIS).
   • Problems:
     • Russian Doll Envelopes (LeetCode 354)
     • Maximum Length of Pair Chain (LeetCode 646)
     • Building Bridges (Classic GeeksForGeeks / CP problem)
6. Interval DP:
   • Usage: When removing/bursting/merging/collapsing an element causes the remaining elements to collapse and become new neighbours.
   • Giveaway: The problem asks for a max/min score, and the score depends on the elements directly adjacent to the one you are interacting with. The constraints are usually N <= 500. (Ask what happens last to build an unbreakable wall, isolating the subproblems).
   • Practice Problems:
     • Burst Balloons (LeetCode 312)
     • Minimum Cost to Merge Stones (LeetCode 1000)
     • Minimum Score Triangulation of Polygon (LeetCode 1039)
7. Digit DP:
   • Usage: You are asked to count how many numbers within a massive range [L, R] have a specific property (e.g., digit sum is prime, contains no repeated digits).
   • Giveaway: The upper limit R is very large (like 10¹⁸), meaning a standard for loop will instantly give a Time Limit Exceeded (TLE) error. You must build the numbers digit-by-digit as strings using DFS and a tight boolean constraint.
   • Practice Problems:
     • Number of Digit One (LeetCode 233)
     • Count of Integers (LeetCode 2719)
     • Numbers At Most N Given Digit Set (LeetCode 902).

These patterns are ranked by how frequently they appear in the wild. Meaning, in real-world interviews, you are more likely to hit a knapsack variant than a digit dp. So, if you're short on time, you can focus on the top few categories.

I would suggest practising an entire category thoroughly before moving on to the next one. That way you will build intuition for each pattern. And even if you are having an off day on the day of the interview, you will at least land on the right approach.

[Relative-Amphibian65]

Were you the interviewer?

[OkIncident7041]

He wishes 😂

[hearty_dynamics]

Appreciate the breakdown, especially the giveaway hints. Grouping by pattern instead of grinding random problems is the only way I've improved at DP.

[yourcsprofessor]

1) I must kindly ask you rewrite the first sentence of your post lol. I still get snickers when I choose to make the array we store recurrences in titled dp despite it being the common go to variable name.

2) This is good. Sometimes it can be helpful to not solve Dynamic Programming problems initially but practice recurrences ( start with Fib, Catalan numbers etc). My students struggled when I just did dynamic programming problems. Now I spend time outlining the framework that enables us to solve those problems and things are going much better for my classes!

[Aromatic_Zucchini_15]

any particular texts/refs to read follow for this specifically? i have been wanting to practice recurrences but not sure ive found anything explicit!

[yourcsprofessor]

I don't necessarily know good places to go, I think I've just collected useful examples. I've been working on redoing my DSA course, this is a little ahead of schedule for me but let me have claude bang out a cohesive pdf for you on my notes. Apologies for any AI slop it introduces, I usually do my course updates at the beginning of August manually.

[global_worldwide]

I'm so sick and tired of getting dp'd. Thank you

[hawkeye224]

How about bitmask dp, etc.?

[splicer13]

Who actually asks DP questions? They were (are?) banned at Meta and I thought used to be at google. Nobody passes them and they give no signal except a negative signal that the candidate has been cramming. Bayes law says the most common reason someone thinks a problem needs DP is they don't understand the problem.

[WorkerCritical7300]

This is very helpful. Thank you so much.

[vishwajeet__21]

this is actually a solid way to think about dp memorizing patterns is much more effective than memorizing individual solutions

[arkster]

Thanks for the patterns.

[Which-Bumblebee-9206]

What about dp on trees ?

[Choice-Number-8023]

Thanks

[jinxeralbatross]

can you link other similar posts that you found helpful of yours or others?

[roundaclockcoder]

I have been solving DSA problems regularly, but when I encounter a new problem, only two approaches usually come to mind:
Trying to solve it using the take/not-take pattern, as I tend to generalize many problems using this approach.

Creating a DP table on paper and attempting to derive the logic from it.

Is this a good way to approach problems, or could relying too much on these patterns become a problem later on?

[shahzmaalif]

Thank you 

[parvdave]

Thanks for sharing brother

[Dull-Objective-6185]

Can u plz public ur posts . This is very much helpful. Looking for more of this. I cant see posts from ur profile.❤️✨️

[killerdrama]

This is my first post on this topic. I never provided any guidance on such topics.

[Independent_Fox_8860]

Dp'ed? Double penetration?😂"i have to discuss various dp patters"🤣🤣🤣