Most people who struggle with DP aren't struggling with the concept. They're struggling with a specific problem: every DP problem looks different on the surface, and nobody teaches you how to recognize which type you're dealing with before you start coding.
This post fixes that. There are 5 structural patterns that cover the vast majority of DP problems in coding interviews. Once you can place a problem in one of these 5 categories, the recurrence almost writes itself.
Why DP feels different from other patterns
Sliding window and two pointers have visible triggers. "Contiguous subarray" means sliding window. "Sorted array, find a pair" means two pointers. The signal is in the problem statement.
DP problems don't work that way. The signal isn't a word in the problem, it's a structural property: overlapping subproblems and optimal substructure. You have to recognize that the problem decomposes into smaller versions of itself, and that solving those smaller versions once (and reusing the answers) leads to an efficient solution.
That's why DP problems feel hard to categorize. But they do fall into patterns, and recognizing those patterns is a learnable skill.
The 5 DP patterns
1. Linear DP (1D state)
The simplest form. Your state is a single index into a 1D array, and each state depends on a fixed number of previous states.
Trigger: the problem asks for the optimal value at position i, and that value depends on positions before i.
Examples: Climbing Stairs, House Robber, Maximum Subarray (Kadane's), Coin Change.
The recurrence for House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). At each house you either skip it (take dp[i-1]) or rob it (take dp[i-2] plus the current value). Two choices, pick the better one.
2. Grid DP (2D state)
Your state is a cell (i, j) in a 2D grid, and you can typically only move right or down. Each cell's value depends on the cells above it and to its left.
Trigger: the problem involves a grid, a matrix, or two sequences being compared.
Examples: Unique Paths, Minimum Path Sum, Longest Common Subsequence, Edit Distance.
The recurrence for Unique Paths: dp[i][j] = dp[i-1][j] + dp[i][j-1]. The number of ways to reach (i,j) is the sum of ways to reach the cell above and the cell to the left.
3. Knapsack DP
You have a set of items, each with a weight and a value, and a capacity. You're deciding which items to include to maximize value without exceeding capacity.
Trigger: "you can use each item once" or "unlimited copies of each item." The subset selection under a budget constraint.
Examples: 0/1 Knapsack, Unbounded Knapsack, Partition Equal Subset Sum, Target Sum.
The two variants matter: 0/1 knapsack (each item used at most once) iterates the capacity in reverse. Unbounded knapsack (unlimited copies) iterates forward. Mixing these up is one of the most common DP bugs.
4. Interval DP
Your state is a subarray or interval (i, j), and the answer for the full interval is built from answers to smaller intervals inside it.
Trigger: the problem asks you to process a sequence and make decisions about ranges within it, where the optimal split point varies.
Examples: Burst Balloons, Matrix Chain Multiplication, Palindrome Partitioning II, Strange Printer.
These are the hardest DP problems in interviews. The key is identifying that you need to try every possible split point k in the range (i, j) and take the best result.
5. State machine DP
Your state includes not just a position but a mode or status the algorithm is in. Transitions change both the position and the mode.
Trigger: the problem involves states like "holding" or "not holding," "in cooldown" or "ready," "ascending" or "descending."
Examples: Best Time to Buy and Sell Stock (with cooldown, transaction limits), Wiggle Subsequence.
The most common example: stock trading with a cooldown. States are: held (holding a stock), sold (just sold, in cooldown), rest (not holding, not in cooldown). Each day you transition between states based on the action you take.
What recognizing the pattern actually changes
Before knowing these patterns, a DP problem looks like: "I need to find some optimal value, I don't know how to start."
After knowing them, it looks like: "This is a 1D linear DP, the state is the index, the transitions are the two choices at each position, the base case is index 0."
That's not a small difference. The pattern gives you the shape of the solution before you've written a line of code. The recurrence is just filling in the details.
The remaining hard part is the base case and the table fill order, which is where most bugs actually live. Getting those right comes from tracing the dp table manually on a small example, watching each cell compute from the ones it depends on.
If you want to go deeper on all 5 patterns with worked examples and a visual walkthrough of how each dp table fills, this guide covers them in detail: Dynamic Programming Explained Visually: Memoization, Tabulation, and the Patterns That Stick
FAQ
Is dynamic programming just recursion with memoization?
Memoization (top-down) and tabulation (bottom-up) are two implementations of the same idea: solve each subproblem once and reuse the result. Memoization uses recursion with a cache. Tabulation fills a table iteratively. Both give the same time complexity. Tabulation is usually faster in practice due to no recursion overhead.
What is the hardest part of dynamic programming?
For most people it's not the recurrence, it's identifying that a problem requires DP at all. The trigger is overlapping subproblems: if a naive recursive solution recomputes the same inputs multiple times, DP is likely the right approach. Draw the recursion tree for a small input and check if nodes repeat.
How do I know if a problem needs DP or greedy?
Greedy works when a locally optimal choice always leads to a globally optimal solution. DP is required when making the locally optimal choice now can lead to a worse outcome later. If you can prove that the greedy choice is safe (often via an exchange argument), use greedy. Otherwise, default to DP.
Originally published at tryexpora.com/blog/dynamic-programming-explained
Top comments (0)