LeetCode DP Guide — Dynamic Programming Problems, Patterns, and Roadmap

Dynamic programming problems appear in approximately 25% of LeetCode Medium and 40% of Hard problems — the single highest-frequency algorithm category in FAANG-level interviews. Yet even engineers who have solved hundreds of LeetCode problems often struggle specifically with DP.

The failure mode is not intelligence — it is sequencing. Most people encounter a hard DP problem early, get stuck, read the solution, feel confused about why it works, and never build real intuition. The solution is not to grind more DP problems — it is to solve them in the right order.

DP problems share a two-part structure: overlapping subproblems (the same smaller problem appears multiple times) and optimal substructure (the optimal solution to the whole is built from optimal solutions to parts). Once you can identify both properties in a problem, DP becomes a mechanical translation process.

This guide gives you the exact problem ladder, the 8 patterns that cover virtually every LeetCode DP problem, and the mistakes that prevent candidates from converting DP knowledge into interview success.

Two properties make a problem a candidate for dynamic programming. The first is overlapping subproblems: the naive recursive solution recomputes the same subproblem repeatedly. The second is optimal substructure: an optimal solution can be constructed from optimal solutions to its subproblems.

The fastest way to identify a DP problem on an interview is to ask: "does a brute-force recursion recompute results?" If you sketch a recursion tree and see the same node appearing at multiple branches, that is overlapping subproblems. If you can define a recurrence relation where a larger answer depends only on smaller answers, that is optimal substructure.

Common DP signals in problem statements: "minimum number of X", "maximum value you can collect", "number of ways to reach", "can you achieve exactly K", "longest subsequence/substring satisfying condition". These phrasings almost always indicate a DP solution exists.

Non-DP problems that look similar: if subproblems are independent (no overlap), divide and conquer is better. If a locally greedy choice always leads to the global optimum, pure greedy beats DP. When in doubt, sketch the recursion tree — if it is a tree with no shared nodes, it is not DP.

The correct order for learning leetcode dp problems is not arbitrary. Each problem builds a specific mental model that makes the next problem easier to see. Skip levels and you will constantly feel like DP solutions appear from nowhere.

Level 1 — Fibonacci (#509): The canonical overlapping subproblems example. F(n) = F(n-1) + F(n-2). Solve it recursive, then memoize it, then tabulate it. This teaches the conversion between all three forms and sets up every DP problem that follows.

Level 2 — Climbing Stairs (#70): Isomorphic to Fibonacci but framed as a counting problem. Teaches you that DP state is "what information do I need to make the next decision." State is the current step; recurrence is ways(n) = ways(n-1) + ways(n-2).

Level 3 — House Robber (#198): First DP problem with a meaningful decision at each step. At each house you choose to rob or skip — introducing the "include or exclude" pattern that appears in half of all DP problems. State: max money at house i. Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Level 4 — Coin Change (#322): Unbounded knapsack variant. Introduces the idea that items can be reused. State is "minimum coins to make amount X." Key insight: dp[amount] = min over all coins of dp[amount - coin] + 1. This forces you to think about state as an amount, not a position.

Level 5 — Longest Common Subsequence (#1143): First 2D DP problem. State is dp[i][j] = LCS length of first i chars of s and first j chars of t. Teaches you how to build a 2D table and how to trace back through it to reconstruct the actual subsequence.

Level 6 — Edit Distance (#72): Builds directly on LCS intuition. Three operations (insert, delete, replace) become three transitions. This is one of the most frequently asked DP problems in actual FAANG interviews and a must-know for any serious candidate.

Level 7 — Unique Paths (#62): 2D grid DP. State is dp[r][c] = number of paths to reach cell (r,c). Trivial recurrence, but teaches the grid traversal order and how to handle boundary conditions cleanly.

Level 8 — 0/1 Knapsack (classic): Each item can be used at most once. State is dp[i][w] = max value using first i items with capacity w. The foundation for dozens of LeetCode Hards including Partition Equal Subset Sum, Target Sum, and Last Stone Weight II.

After working through the ladder, every new DP problem you encounter will belong to one of eight patterns. Identifying the pattern is the first step in any DP interview question — it tells you what state to define and what transitions to write.

Pattern 1 — Linear 1D DP: State is a single index into an array. Problems: Climbing Stairs (#70), House Robber (#198), Jump Game, Decode Ways. Recurrence looks back 1-2 positions. Space can often be reduced to O(1) by keeping only the last two values.

Pattern 2 — Linear 2D DP: State is two indices, often into two strings. Problems: LCS (#1143), Edit Distance (#72), Distinct Subsequences, Interleaving String. Build an (m+1) x (n+1) table. Fill row by row, referencing the row above and the current row.

Pattern 3 — Knapsack: State includes a "capacity" or "budget" dimension. Problems: Coin Change (#322), Partition Equal Subset Sum, Target Sum, Last Stone Weight II. Decide whether to include each item; capacity decreases or budget changes with each inclusion.

Pattern 4 — LCS/Edit Distance family: String transformation and alignment problems. Transition involves matching, inserting, deleting, or replacing characters. The 2D table represents alignment state between two strings or sequences.

Pattern 5 — Interval DP: State is dp[i][j] = answer for the subarray/substring from i to j. Problems: Burst Balloons, Matrix Chain Multiplication, Palindrome Partitioning II, Strange Printer. Enumerate a split point k in [i,j]. These are often the hardest DP problems because the state space is O(n^2) and each transition is O(n).

Pattern 6 — Tree DP: DP on trees, where state at a node depends on its children. Problems: House Robber III, Binary Tree Cameras, Maximum Sum BST. Requires post-order DFS — compute children state first, then combine at the current node.

Pattern 7 — Digit DP: Count integers in a range satisfying a digit-level constraint. Problems: Non-negative Integers without Consecutive Ones, Count Numbers with Unique Digits. State tracks position, tight constraint, and whatever digit property matters.

Pattern 8 — Bitmask DP: State includes a bitmask representing a subset of elements. Problems: Traveling Salesman (TSP) variants, Partition to K Equal Subset Sum. Used when n is at most 20 and you need to track which elements have been used or visited.

Every DP problem can be approached top-down (memoization) or bottom-up (tabulation) — interviewers typically prefer bottom-up for absence of stack overflow risk. Understanding when to use each and how to convert between them is an expected skill at the senior level.

Memoization (top-down): Write the natural recursion, add a cache (dict or array). Call recursively; if the result is already cached, return it immediately. The call stack grows to O(recursion depth). For problems with n up to 10,000, stack overflow is a real risk in Python. The upside: you only compute states that are actually reachable, which matters in sparse state spaces.

Tabulation (bottom-up): Identify the base cases, create a table initialized to the base values, fill the table in an order where dependencies are always computed before they are needed (usually left-to-right or top-to-bottom). No recursion, no stack overflow, and often cache-friendlier due to sequential memory access.

The conversion recipe: take your memoized solution, look at the cache key (that is your state), identify the smallest subproblems (those are your base cases), find the iteration order (reverse the recursive dependency direction), then translate each recursive call into a table lookup.

In interviews: start with memoization to establish correctness quickly, then convert to tabulation if asked about optimization. Mention space optimization as a bonus — many 2D DP tables can be reduced to O(n) by noting that each row only depends on the previous row.

Mistake 1 — Starting with base cases before the recurrence. Many candidates initialize dp[0] and dp[1] by gut feeling, then try to find a recurrence that fits. The correct order is: define what dp[i] means precisely, derive the recurrence algebraically, then identify what makes the recurrence break down (those are the base cases).

Mistake 2 — Wrong dimensionality. Choosing 1D when 2D is needed (or vice versa) is a structural error that cannot be patched. If your state does not carry enough information to make a decision at each step, add a dimension. If two state variables always move together, they can often be collapsed into one.

Mistake 3 — Confusing the recurrence direction. For LCS (#1143) and Edit Distance (#72), many candidates mix up dp[i][j] depending on dp[i-1][j] vs dp[i][j-1] vs dp[i-1][j-1]. Draw the dependency arrows explicitly before coding — they determine your fill order.

Mistake 4 — Off-by-one errors in initialization. Using 0-indexed vs 1-indexed inconsistently, or forgetting to size the dp array as n+1 to handle the "empty" base case. A clean convention: 1-indexed arrays where dp[0] represents the empty case, and fill from dp[1] to dp[n].

Mistake 5 — Not recognizing a DP problem as one of the 8 patterns. If you see a problem and think "I need a completely new approach," that is a signal to re-examine whether it fits a known pattern with a different framing. Burst Balloons looks nothing like Coin Change (#322), but both are DP — the difference is interval DP vs knapsack.

Mistake 6 — Skipping the brute-force step. Jumping straight to DP without writing the exponential recursive solution first is slower, not faster. The brute-force gives you the recurrence for free. Memoize it, then convert to tabulation. This three-step process is reliable; writing tabulation directly from a problem statement is error-prone.

DP mastery is achievable in 6-8 weeks with the right structure. Weeks 1-2: work through the 8-problem ladder above, one problem per day, implementing each in memoization and tabulation. Do not move on until you can write both forms from scratch without referring to solutions.

Weeks 3-4: solve 3-4 problems per pattern from the 8 core patterns. Focus on Linear 1D, 2D, and Knapsack first — these cover roughly 60% of interview DP problems. Weeks 5-6: Interval DP (Burst Balloons is mandatory), Tree DP (House Robber III), and review edge cases in state definition.

Weeks 7-8: timed practice. Give yourself 20-25 minutes per Medium DP problem. If you cannot identify the pattern within 5 minutes, that is the skill to practice — pattern recognition, not solution memorization.

Use spaced repetition to retain what you learn. YeetCode tracks which DP problems you have mastered and which need review, scheduling them at the optimal interval to move knowledge into long-term memory. DP is a skill that degrades without review — a problem you solved confidently last month may feel foreign today if you have not revisited the pattern.

The candidates who ace DP interviews are not the ones who memorized 50 DP solutions. They are the ones who deeply internalized the 8 patterns and can derive a new solution from first principles in 20 minutes. That depth comes from the ladder approach, not from random grinding across hundreds of problems.