DP patterns for interviews

These 10 DP patterns for interviews cover 90% of dynamic programming questions. Learn each pattern's invariant and how to recognize it on sight.

10 minutes

Intermediate

What you will learn

Why 10 patterns cover 90% of DP interview problems

The invariant and identification trigger for each pattern

How to derive a recurrence from the pattern's invariant

Common mistakes that prevent DP patterns from sticking

Most engineers study DP patterns for interviews by 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.

⚡TL;DR

Ten DP patterns cover roughly 90% of dynamic programming interview problems. Each has a distinct invariant that tells you when it applies and how to build the recurrence. This article covers all ten with their identification triggers and canonical problems.

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.

10 DP patterns that cover 90% of interview problems

Linear DP

Sequential state transitions over a 1D sequence (count ways, min/max cost)

Coin Change

Unbounded or bounded choices to reach a target sum

Longest Common Subsequence

Character-by-character comparison of two sequences

Longest Increasing Subsequence

Ordering constraints within a single sequence

Edit Distance

Minimum character-level transformations between two strings

Subset Sum

Binary include/exclude decisions to reach a target

0/1 Knapsack

Include/exclude items under a capacity constraint to maximize value

2D Grid DP

Path counting, min cost, or region size on a matrix

Prefix Sum DP

Precomputed cumulative sums for O(1) range queries

Game Theory DP

Two players alternating turns with optimal play

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.

Invariant

Linear DP
Each state depends on a fixed number of previous states
Coin Change
Repeatable selections from a set to hit a target
LCS
Match or skip, character by character, across two sequences
LIS
Extend the best sequence ending before the current position
Edit Distance
Insert, delete, or replace to align two strings
Subset Sum
Include or exclude each element, tracking reachable sums
0/1 Knapsack
Include or exclude each item, tracking remaining capacity
2D Grid DP
State at cell (i,j) depends on adjacent cells
Prefix Sum DP
Cumulative sums enable constant-time range calculations
Game Theory DP
First player maximizes, second minimizes, alternating

Identification trigger

Linear DP
"Count ways" or "min cost" over consecutive elements
Coin Change
"Minimum items to reach sum X" or "ways to form total X"
LCS
Two strings/arrays, "longest shared subsequence" preserving order
LIS
Single sequence, "longest strictly increasing run"
Edit Distance
"Minimum operations" to convert one string to another
Subset Sum
"Can you select elements to reach target X?" or "partition equally"
0/1 Knapsack
Fixed capacity, items with weight/value, "maximize total"
2D Grid DP
Grid traversal asking for paths, cost, or area
Prefix Sum DP
"Sum of subarray/submatrix" with repeated queries
Game Theory DP
Two optimal players, asking for best possible outcome

Canonical problem

Linear DP
Covering Distance
Coin Change
Coin Change
LCS
Longest Common Subsequence
LIS
Longest Increasing Subsequence
Edit Distance
Edit Distance
Subset Sum
Subset Sum
0/1 Knapsack
Zero One Knapsack
2D Grid DP
Destination Path Count
Prefix Sum DP
Maximum Submatrix Sum
Game Theory DP
Optimal Game Strategy

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.

💡 Tip

The identification trigger column matters most during interviews. When you read a new problem, scan for these structural signatures before thinking about code.

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.

Python

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.

The mistakes that keep DP patterns from sticking

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

Memorizing recurrences without understanding invariants: You can memorize the LCS recurrence. But if you don't understand why a match extends from dp[i-1][j-1] while a non-match takes max(dp[i-1][j], dp[i][j-1]), you won't adapt when the problem adds a twist. Wildcard Pattern Matching, for example, uses the same two-string invariant but adds a * character that changes the transition. Without the invariant, the twist is a wall. With it, the modification is straightforward.
Skipping the identification step: Most engineers jump from reading the problem straight to attempting code. The identification step, where you scan for structural triggers and match them to a pattern, is the layer that makes DP fast under pressure. Without it, you're reverse-engineering the pattern from the problem every single time.
Practicing patterns in isolation instead of interleaving: Solving 10 LCS problems in a row builds familiarity with LCS. It doesn't build the ability to distinguish LCS from Edit Distance when both problems involve two strings. Interleaving practice across pattern families trains the selection skill, which is what interviews actually measure. Isolation practice feels productive because you get faster at each individual pattern. But the interview doesn't test speed within a pattern. It tests whether you can pick the right one.

“The interview doesn't test whether you know the LCS recurrence. It tests whether you can identify that LCS is the right pattern before anyone tells you.”

The identification gap

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 identification 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, with 63 lessons, 85 problems, and 15 patterns included. 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.

Do you want to master data structures?

Try our data structures learning path made of highly visual and interactive courses. Get hands on experience by solving real problems in a structured manner. All resources you would ever need in one place for FREE

Start Learning

Ten cover roughly 90% of what shows up: Linear DP, Coin Change, LCS, LIS, Edit Distance, Subset Sum, 0/1 Knapsack, 2D Grid DP, Prefix Sum DP, and Game Theory DP. If you know these ten with their invariants, you'll have the tools for most DP questions you'll face.

Both use an include/exclude invariant where you decide whether to include each element. Subset Sum asks "can you reach this target?", a yes/no question. Knapsack adds a capacity constraint and an optimization objective: maximize total value without exceeding the weight limit. The recurrence shapes are similar, but Knapsack tracks remaining capacity as an additional state dimension, which makes its DP table two-dimensional.

Start with Linear DP and Coin Change because their invariants are the simplest and build intuition for state transitions. Then move to LCS and LIS, which introduce two-sequence and single-sequence comparison. Edit Distance, Subset Sum, and Knapsack follow naturally from there. Save Grid DP, Prefix Sum DP, and Game Theory DP for last, since they combine DP with spatial reasoning or adversarial thinking.

Understanding a solution is recognition, which is passive. Constructing one requires you to identify the invariant, define the state, and derive the transition from scratch. Most engineers practice by reading solutions, which trains recognition but not construction. To close that gap, you need to practice the derivation process itself, not just review the final answer.

Scan the problem for identification triggers. Two strings suggests LCS or Edit Distance. A target sum with element selection suggests Subset Sum or Knapsack. A grid with path counting suggests 2D Grid DP. The invariant table in this article gives you the structural signature to match against. With practice, this identification becomes fast enough to happen in the first 30 seconds of reading a problem.

DP has that reputation, but much of it comes from how it's typically taught. Most resources show finished solutions without explaining the invariant that produced them. When you learn DP through invariants and identification triggers instead of memorization, the difficulty drops because you're constructing solutions from a principle rather than trying to retrieve them from memory.