Dynamic programming terrifies more candidates than any other coding-interview topic — and for good reason. A single DP question can collapse in the first five minutes if you cannot recognize the underlying pattern. The good news is that nearly every DP problem you will face at Google, Amazon, Meta, Stripe, or a top series-B startup in 2026 reduces to one of a small number of templates. Learn the templates, and the problem becomes pattern-matching plus careful indexing.
This guide breaks down the seven dynamic programming patterns that account for the overwhelming majority of DP questions asked in tech interviews today, with recurrence relations, base cases, and representative LeetCode problems for each. Use it as your single-page reference for your next coding loop.
Why Pattern Recognition Beats Memorization
Interviewers almost never invent DP problems from scratch; they pull variants from a well-known corpus. What changes is the framing — a knapsack problem becomes a budget allocation problem, longest common subsequence becomes a DNA edit problem, and house robber becomes a coin-selection problem. If you memorize 200 solutions, you will forget 180. If you internalize the seven templates below, you can derive any solution on the whiteboard.
Before we start: every DP solution has three moving parts you must be able to articulate out loud — the state (what the subproblem represents), the transition (how smaller subproblems combine), and the base case (where the recursion bottoms out). If you cannot state these three in plain English, do not write code yet.
Pattern 1: Linear DP (1D State)
The simplest family. dp[i] represents the answer to a subproblem ending at — or involving — the first i elements. The transition usually looks back a constant number of steps.
Recurrence template: dp[i] = f(dp[i-1], dp[i-2], ..., dp[i-k])
Canonical problems: Climbing Stairs (LC 70), House Robber (LC 198), Fibonacci, Decode Ways (LC 91), Maximum Subarray via Kadane (LC 53).
Recognition cues: Single array input, question asks for an optimum (max/min/count) up to each index, each element has a local “include or skip” decision.
Time complexity: typically O(n). Space can usually be compressed from O(n) to O(1) because only the last few states matter.
Pattern 2: Grid / 2D DP
dp[i][j] represents the answer for the sub-grid ending at cell (i, j). Transitions draw from adjacent cells — usually top, left, and diagonal.
Recurrence template: dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
Canonical problems: Unique Paths (LC 62), Minimum Path Sum (LC 64), Maximal Square (LC 221), Dungeon Game (LC 174).
Recognition cues: 2D board or grid input, movement restricted to right/down (or four directions with obstacles), question asks for a count of paths or optimum path cost.
Pattern 3: Knapsack — 0/1 and Unbounded
Knapsack is the most tested DP family for a reason: it models every “choose a subset under a capacity” question. There are two flavors.
0/1 Knapsack — each item can be taken at most once. dp[i][w] is the best value using the first i items with capacity w.
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
Unbounded Knapsack — items are reusable. The only change is pulling from the current row instead of the previous one:
dp[i][w] = max(dp[i-1][w], dp[i][w - weight[i]] + value[i])
Canonical problems: Partition Equal Subset Sum (LC 416), Target Sum (LC 494), Coin Change (LC 322, unbounded), Coin Change II (LC 518), Perfect Squares (LC 279).
Recognition cues: The phrase “using these items,” a capacity or target sum, asking whether a subset achieves a value, how many ways, or the minimum count.
Pattern 4: Subsequence DP
Given one or two sequences, find an optimal subsequence. The state is typically dp[i][j] where i and j are prefix lengths of the two strings.
Recurrence template (two-string variant):
if s1[i] == s2[j]: dp[i][j] = dp[i-1][j-1] + 1else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Canonical problems: Longest Common Subsequence (LC 1143), Edit Distance (LC 72), Longest Increasing Subsequence (LC 300), Distinct Subsequences (LC 115), Delete Operation for Two Strings (LC 583).
Recognition cues: Two strings or arrays, the word “subsequence” or “transform,” operations like insert/delete/replace.
Pro tip: LIS has an elegant O(n log n) solution using binary search over a “patience sort” stack — memorize it; it surfaces in senior-engineer rounds.
Pattern 5: Interval / Range DP
State is an interval dp[i][j] representing the optimum over the range [i, j]. You iterate by interval length, not by index. Transitions split the interval at some pivot k.
Recurrence template: dp[i][j] = min/max over k in (i, j) of (dp[i][k] + dp[k][j] + cost)
Canonical problems: Matrix Chain Multiplication, Burst Balloons (LC 312), Palindromic Substrings (LC 647), Longest Palindromic Subsequence (LC 516), Minimum Cost to Cut a Stick (LC 1547).
Recognition cues: The problem involves merging, cutting, or bursting elements inside a range, and order of operations matters. Time complexity is typically O(n³).
Pattern 6: Tree DP
The “DP on trees” pattern processes a rooted tree bottom-up with post-order recursion. State is defined per node, often with multiple variants per node (e.g., “best answer including this node” vs. “excluding this node”).
Template:
def dfs(node):
if not node: return base_case
left = dfs(node.left)
right = dfs(node.right)
return combine(node.val, left, right)
Canonical problems: House Robber III (LC 337), Binary Tree Maximum Path Sum (LC 124), Diameter of Binary Tree (LC 543), Longest Univalue Path (LC 687).
Recognition cues: Input is a tree, the answer at each node depends on children, you often need to return a tuple describing multiple sub-states.
Pattern 7: Bitmask DP
When the input size is small (usually n ≤ 20), you can encode a subset of elements as the bits of an integer. State is often dp[mask] or dp[mask][i].
Recurrence template: dp[mask] = min/max over all last elements j in mask of (dp[mask ^ (1<<j)] + cost(j, ...))
Canonical problems: Traveling Salesman (classic), Partition to K Equal Sum Subsets (LC 698), Shortest Path Visiting All Nodes (LC 847), Can I Win (LC 464), Minimum Cost to Connect Two Groups of Points (LC 1595).
Recognition cues: Small n, a set of objects where order of selection matters, the phrase “visit all” or “assign each.”
A Practice Plan That Actually Works
Most candidates grind random LeetCode lists and plateau. A tighter plan: pick one pattern per week, solve four problems — one easy, two medium, one hard — and write out the recurrence before coding. After the fourth problem, close your editor and re-derive the recurrence on paper. If you can do that, the pattern is yours.
For mock-interview practice, pair with a peer and verbalize your three-part framework (state, transition, base case) before writing code. If you use a real-time assistant like Niraswa AI during practice rounds, treat it as a safety net for cue questions you miss — not a replacement for the thinking work.
Common Mistakes That Sink DP Answers
Three mistakes tank an otherwise-strong DP solution in interviews: jumping to code before stating the recurrence, conflating the problem dimension with the state dimension (a 2D input does not always need a 2D state), and ignoring space optimization on a question where the interviewer clearly expects it. The fix for all three is the same — slow down for the first five minutes and narrate your reasoning out loud.
Closing: Recognize, Don’t Memorize
Dynamic programming is pattern recognition dressed up as mathematics. Master the seven templates above, practice articulating state, transition, and base case in under sixty seconds, and you will walk into your next coding interview with something rarer than raw talent: calm. Bookmark this page, work through one problem from each pattern this week, and revisit it the night before any onsite.
Ready to level up your coding interview prep? Start solving one problem from each of the seven patterns above today. Share this guide with a peer who is prepping for interviews — the fastest way to learn a pattern is to teach it.
