The 10 Most Important DP Patterns for Interviews

Studying DP patterns for interviews usually starts with memorizing specific recurrences. Learn the coin change formula, learn the knapsack template, hope the problem matches one you've drilled. That works right up until the problem is unfamiliar. Then you're stuck.

The gap isn't about knowing more patterns. It's about understanding what each pattern's invariant is, the structural property that produces the recurrence. When you know the invariant, you don't need to remember the solution. You can derive it.

Why DP patterns matter more than problem count

Dynamic programming problems feel wildly diverse on the surface. A grid path problem looks nothing like a string transformation problem. A coin change variant has no visible connection to an edit distance variant. But underneath, most DP interview questions fall into one of ten pattern families that share more than a name.

Each family shares an invariant, the core property that determines how subproblems relate to each other. When you recognize it, you know the shape of the recurrence before writing any code. When you don't, you're guessing.

Ten DP patterns cover roughly 90% of the dynamic programming problems that appear in FAANG interviews: Linear DP, Coin Change, Longest Common Subsequence, Longest Increasing Subsequence, Edit Distance, Subset Sum, 0/1 Knapsack, 2D Grid DP, Prefix Sum DP, and Game Theory DP. Each has a distinct invariant that determines when it applies and how to build the recurrence.

Instead of grinding 50 random DP problems, you can learn 10 invariants and apply them to any problem in their family. Each invariant tells you the recurrence shape before you write a single line of code. Once you've internalized that, unfamiliar problems stop feeling random.

The 10 DP patterns and what each one solves

All ten, grouped by the class of problem each one addresses.

The difference between knowing a pattern exists and being able to use it is the invariant. Below is what drives each one, along with the identification triggers that tell you which pattern a new problem belongs to.

A few patterns blur at the edges. Subset Sum and 0/1 Knapsack share the include/exclude invariant, but Knapsack adds a capacity dimension and an optimization objective. LCS and Edit Distance both compare two strings, but their recurrence shapes diverge because Edit Distance allows three operations while LCS only allows match or skip. Knowing where these boundaries sit is part of what makes the patterns usable rather than decorative knowledge.

How invariants drive pattern identification

Knowing the pattern name isn't enough. You need to see how the invariant produces the recurrence, because that's the skill interviews actually test.

You're given two strings, "ABCBDAB" and "BDCAB". The problem asks for the length of the longest subsequence common to both, where order must be preserved but characters don't need to be contiguous.

The invariant: At every position, you compare one character from each string. If they match, the answer extends. If they don't, you take the best result from dropping one character from either string.

That invariant directly produces the recurrence. The state definition follows from that comparison logic. dp[i][j] represents the LCS length for the first i characters of string A and the first j characters of string B. The transition follows from the match or skip property.

Look at what the invariant gave you. "Match or skip, character by character" told you the state definition, the transition, and the base case. You didn't memorize the recurrence. You derived it from a single core property. On Codeintuition, the understanding lesson for LCS walks through this exact derivation frame by frame, tracing variable state at every step before you attempt any problems.

Every pattern in the table works the same way. Coin Change's invariant ("repeatable selections to hit a target") produces a different recurrence shape. 0/1 Knapsack's ("include or exclude under capacity") produces yet another. But the process is always: identify the invariant, define the state, derive the transition.

What changes when you apply invariants under time pressure

Knowing the invariant during a calm study session is one thing. Using it when you've got 20 minutes left and the interviewer is watching is different.

Without the invariant, your first 5 minutes on an unfamiliar DP problem are spent staring at examples, trying brute force, maybe spotting a recursion, then figuring out what state to track. With the invariant, you read the problem, match the structural trigger, and you've already got the recurrence shape. The remaining time goes toward edge cases and optimization, not discovery.

That difference compounds when problems combine patterns. If you don't have the base invariant internalized, you're solving two problems at once: figuring out the base pattern and handling the twist. If you do, you're only solving one. The base recurrence is already in your head. You're just adjusting the special case.

Time pressure also changes how you communicate. When you can say "this is a two string comparison problem, so the state is dp[i][j] representing the first i characters of each input," you've shown your thought process in one sentence. That's harder to do when you're still figuring out the state definition yourself.

Practice starting from the identification trigger and reaching a working recurrence within 3 minutes. That's the bridge between "I know the patterns" and "I can use them when it counts."

The mistakes that keep DP patterns from sticking

Three mistakes account for most of the frustration engineers feel with DP.

When patterns overlap and how to tell them apart

Some DP problems sit right at the boundary between two patterns. That's where most wrong turns happen, not because you don't know any pattern, but because you pick the adjacent one.

The most common confusion is between Subset Sum and 0/1 Knapsack. Both involve scanning through items and deciding to include or exclude each one. The difference is the objective. Subset Sum asks a boolean question: can you reach this target? Knapsack asks an optimization question: what's the maximum value within a capacity limit? If the problem says "partition into two equal subsets," that's Subset Sum. If it says "maximize profit without exceeding weight," that's Knapsack. The invariant is similar, but the state diverges. Subset Sum tracks dp[i][s] as true or false. Knapsack tracks dp[i][c] as a numeric maximum.

Another frequent overlap: LCS versus Edit Distance. Both compare two strings character by character. But LCS only has two transitions (match or skip), while Edit Distance has three (insert, delete, replace). When the problem mentions "minimum operations" or "convert string A to string B," you're in Edit Distance territory. When it mentions "longest shared subsequence" preserving order, you're in LCS territory. The trigger isn't two strings existing. It's whether the problem asks you to align them or transform one into the other.

Getting comfortable with these boundaries means practicing problems that sit near them and articulating why one pattern fits and the other doesn't.

From recognition to derivation

This article covers what each DP pattern is and how to recognize it. For the complete treatment of how to derive recurrences from scratch, prove correctness, and handle the edge cases that separate Medium from Hard, see the complete guide to dynamic programming.

DP builds on recursion. If the connection between recursion and the tabulation table isn't clear yet, understanding recursion from first principles is the step that makes DP click.

Codeintuition's Dynamic Programming course covers all 10 patterns across 38 problems. Each pattern follows the same sequence: understand the invariant, learn the structural triggers, then apply with increasing difficulty. The course sits inside the full learning path that builds DP on top of recursion, which builds on the data structures that DP problems depend on.

The first two courses (Arrays and Singly Linked Lists) are free, covering 63 lessons and 85 problems where you can practice the invariant first approach on foundational patterns before tackling DP. Premium unlocks the rest for $79.99/year ($6.67/month).

Before understanding invariants, every new DP problem feels like a coin flip. You've either seen it or you haven't. After, you read a problem, spot the structural trigger, and know which recurrence shape to build before writing any code. That shift doesn't come from more practice. It comes from the right kind.