Dynamic Programming Patterns: How to Recognize and Solve DP Problems
From Optimal Substructure to State Machines: A Pattern-First Framework for Cracking Any DP Interview Question
What You Must Master to Clear This Track
- Confirm optimal substructure and overlapping subproblems exist before reaching for DP; if subproblems don't repeat, you likely just need greedy or divide-and-conquer.
- Always write the brute-force recursive relation first, identify the state variables, then memoize top-down before converting to a bottom-up table.
- Classify every problem into one of six families: 1D sequence DP, 2D grid DP, knapsack (0/1, unbounded, subset-sum), interval DP, state-machine DP, or tree/graph DP.
- Space-optimize by rolling the DP table down to O(1) or O(N) once you can prove the recurrence only depends on the previous row or a fixed window of prior states.
- In interviews, narrate your state definition (dp[i] means...) out loud before coding — most DP failures come from an ambiguous state definition, not bad code.
Step-by-Step Study Plan
Follow this sequential roadmap designed to take you from core foundations to advanced architecture and mock interviews.
Spotting DP and Mastering Linear State Transitions
Learn the two-question test for DP (does an optimal solution reuse optimal solutions to smaller subproblems, and do subproblems repeat), then drill 1D sequence problems like Climbing Stairs, House Robber, and Longest Increasing Subsequence.
- •Write the brute-force recursion tree for Fibonacci and Climbing Stairs and manually count duplicated calls to internalize 'overlapping subproblems.'
- •Solve the House Robber family (linear array, circular array, binary tree houses) using a single dp[i] = max(dp[i-1], dp[i-2] + nums[i]) transition.
- •Implement both top-down memoized and bottom-up tabulated versions of the same problem and compare call stack depth vs iteration count.
- •For every problem, write dp[i] = ... in plain English before writing any code.
- •Time-box yourself to identify the state and transition within 5 minutes before attempting the code.
Multi-Dimensional State Spaces and Partitioning Problems
Move to two-dimensional recurrences: grid traversal (Unique Paths, Minimum Path Sum), the full knapsack family (0/1 Knapsack, Coin Change unbounded, Partition Equal Subset Sum), and interval DP (Matrix Chain Multiplication, Burst Balloons, Palindrome Partitioning).
- •Derive dp[i][j] transitions for grid problems and correctly seed the first row/column as base cases.
- •Distinguish 0/1 knapsack (iterate items outer, weights inner, descending) from unbounded knapsack (weights outer, ascending) to avoid reusing items incorrectly.
- •Solve at least 3 interval DP problems using the dp[i][j] = best split over dp[i][k] + dp[k+1][j] + cost(k) pattern, iterating by increasing interval length.
- •Draw the DP table by hand for a small example (N=4 or 5) before coding; verify base cases and fill order.
- •For every knapsack variant, explicitly answer: can an item be reused? Does order of items matter (combinations vs permutations)?
Multi-State Transitions and Production-Grade Efficiency
Master state-machine DP for stock trading problems with cooldowns and fees, extend DP onto trees (House Robber III, Diameter-style aggregation) and DAGs (Longest Path, Longest Common Subsequence as a grid-shaped graph), and compress every solution's space complexity.
- •Model Buy/Sell Stock with Cooldown as a 3-state machine (held, sold, rest) and derive the daily transition equations.
- •Implement post-order DFS DP on a binary tree where each node returns a pair of states (rob this node, don't rob this node).
- •Refactor at least 3 previously-solved 2D DP solutions down to rolling 1D arrays or O(1) scalar variables.
- •Practice explaining why a DP recurrence's dependency footprint (which prior rows/columns it reads) determines how far you can space-optimize.
- •Mock-interview yourself narrating state definition, base case, transition, iteration order, and final answer extraction as five explicit steps.
1. Recognizing DP: Optimal Substructure, Overlapping Subproblems & Top-Down vs Bottom-Up
Before writing a single line of code, a DP problem must pass two structural tests. Skipping this recognition step is the single biggest reason candidates either force DP onto a greedy problem or miss DP entirely and time out with brute force.
The optimal solution to the full problem can be constructed from optimal solutions to its subproblems (e.g., the shortest path to node N uses the shortest paths to N's predecessors). If a locally optimal choice can break global optimality, you may need DP over multiple candidate states instead of a greedy single choice.
The same subproblem is solved repeatedly during naive recursion (e.g., fib(5) calls fib(3) twice). If every subproblem is distinct and never recurs, plain divide-and-conquer (like merge sort) is more appropriate than DP.
Write the natural recursive brute force first, then cache results in a hash map or array keyed by state. Easiest to derive correctly and naturally handles sparse or irregular state spaces.
Iteratively fill a table from base cases upward in a well-defined order, avoiding recursion/call-stack overhead entirely. Required for further space optimization and generally preferred in final interview code.
- State your recurrence in English first: 'dp[i] represents the minimum cost to reach index i' — an ambiguous state definition is the root cause of most DP bugs.
- If you can identify a natural 'last decision' (the last item taken, the last day traded, the last cut made), the DP transition almost always falls out of enumerating that decision's options.
- Jumping to bottom-up tabulation before validating the recurrence with a slower, obviously-correct top-down memoized version.
- Forgetting to initialize base cases correctly (e.g., dp[0] or an empty subset) which silently corrupts every downstream value.
2. 1D DP: Climbing Stairs Family & House Robber
One-dimensional DP problems index the state by a single variable, typically 'position in the array/sequence.' These are the fastest pattern to recognize and the foundation every other DP family builds on.
dp[i] = dp[i-1] + dp[i-2] counts ways to reach step i using 1 or 2 steps; generalizes to Tribonacci, Decode Ways, and any 'count arrangements' problem with a small fixed lookback window.
dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — at each house, either skip it (carry forward the best so far) or rob it (best from two houses back plus current value).
Since the first and last houses are adjacent, run the linear House Robber twice — once excluding the last house, once excluding the first — and take the max, cleanly reducing a circular constraint to two linear subproblems.
dp[i] = 1 + max(dp[j]) for all j < i where nums[j] < nums[i]. O(N^2) naive, but reducible to O(N log N) using patience sorting with a tails array and binary search.
// dp[i] = max(dp[i-1], dp[i-2] + nums[i])
// Rolled down from an O(N) array to two scalar variables.
function rob(nums: number[]): number {
let prevTwo = 0; // dp[i-2]
let prevOne = 0; // dp[i-1]
for (const value of nums) {
const current = Math.max(prevOne, prevTwo + value);
prevTwo = prevOne;
prevOne = current;
}
return prevOne;
}3. 2D Grid DP & The Knapsack Family (0/1, Unbounded, Subset-Sum)
Once state requires two dimensions — position in a grid, or 'items considered so far' crossed with 'capacity remaining' — the table becomes 2D. The knapsack family is the most heavily tested DP archetype because so many real problems (subset sum, coin change, partition) are secretly knapsack in disguise.
dp[i][j] = dp[i-1][j] + dp[i][j-1] (counting paths) or dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) (minimizing cost). First row and first column are base cases seeded directly from the grid.
Each item used at most once: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]). When space-optimizing to a 1D array, you MUST iterate capacity in descending order to avoid reusing an item twice in the same pass.
Each item reusable unlimited times: dp[amount] = min(dp[amount], dp[amount - coin] + 1) for each coin. Iterate capacity ascending (not descending) because reuse of the same item within one pass is exactly what you want.
A specialization of 0/1 knapsack where 'value' equals 'weight': dp[sum] = true if some subset sums exactly to 'sum'. Partition Equal Subset Sum reduces to: does a subset sum to totalSum / 2?
How dp[i][w] fills row by row from the base case up to the final answer at dp[n][capacity].
function knapsack(weights: number[], values: number[], capacity: number): number {
const dp = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
// Descending order: guarantees dp[w - weights[i]] still reflects
// the PREVIOUS item iteration (i-1), not the current one.
for (let w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}- Whenever a problem says 'each element used at most once,' think 0/1 knapsack. 'Unlimited supply' or 'as many times as needed' signals unbounded knapsack.
- Coin Change (minimum coins) and Coin Change II (number of combinations) use the same unbounded knapsack table shape but swap min/sum, and swap the loop nesting order to distinguish combinations from permutations.
4. Interval DP, State-Machine DP & Tree/Graph DP
The most advanced DP category layers extra structure onto the base recurrence: intervals that must be split optimally, an explicit finite-state machine that evolves day by day, or a tree/graph shape that requires post-order aggregation instead of a simple array index.
dp[i][j] represents the optimal answer over the subarray/substring from i to j, computed by trying every split point k: dp[i][j] = best over k of dp[i][k] + dp[k+1][j] + cost(i, k, j). Must iterate by increasing interval length so smaller intervals are ready before larger ones need them.
Model explicit daily states — held, sold-today (triggers cooldown), and resting — each with its own dp array. Transitions read yesterday's OTHER states, mirroring a finite-state automaton's edges.
Post-order DFS where each node returns a tuple of states to its parent, e.g. (maxIfRobbed, maxIfNotRobbed). The parent combines children's states without ever revisiting a subtree, giving O(N) time despite branching structure.
Any DAG admits DP over a topological order: dp[node] = best over predecessors of dp[predecessor] + edgeCost. Longest Common Subsequence is itself a grid-shaped DAG where each cell has edges from its left, top, and diagonal neighbor.
function maxProfit(prices: number[]): number {
if (prices.length === 0) return 0;
// Three explicit states per day:
let held = -prices[0]; // holding a share (max profit so far)
let sold = 0; // just sold today (forces cooldown tomorrow)
let rest = 0; // not holding, not in cooldown
for (let i = 1; i < prices.length; i++) {
const prevHeld = held;
const prevSold = sold;
const prevRest = rest;
held = Math.max(prevHeld, prevRest - prices[i]); // keep holding, or buy from rest
sold = prevHeld + prices[i]; // sell what we were holding
rest = Math.max(prevRest, prevSold); // stay resting, or cooldown just ended
}
return Math.max(sold, rest); // never end the day still holding for max profit
}- Filling an interval DP table in row-major order instead of by increasing interval length, which reads dp[i][k] or dp[k+1][j] before they've been computed.
- In tree DP, returning a single value instead of a tuple of states, which loses the information the parent needs to decide whether including the current node is legal or optimal.
Cracking a Senior SDE Onsite DP Round with a Modified Knapsack Problem
During an onsite loop for a Senior Software Engineer role at a logistics company, a candidate was given a variant of 0/1 Knapsack: select a subset of delivery routes to maximize total revenue under both a weight capacity constraint AND a maximum-routes-count constraint, a twist the candidate had never seen packaged exactly this way before.
- 1Recognized the core shape as 0/1 Knapsack (each route usable at most once) but noted the second constraint (max route count) meant the state needed a third dimension beyond items and capacity.
- 2Stated the state definition out loud: dp[i][w][k] = max revenue considering the first i routes, using at most weight capacity w, and at most k routes selected.
- 3Derived the transition by enumerating the two choices for each route: skip it (dp[i-1][w][k]) or take it (dp[i-1][w-weight][k-1] + revenue), taking the max.
- 4Implemented the brute-force top-down memoized version first using a Map keyed by (i,w,k) to validate correctness against the interviewer's small example.
- 5Converted to bottom-up tabulation once correctness was confirmed, then discussed space optimization: since dp[i] only depends on dp[i-1], the array could be rolled down to two 2D layers (O(capacity * maxRoutes) space instead of O(routes * capacity * maxRoutes)).
- 6Proactively raised the reconstruction question ('if asked which specific routes, I'd need to retain the full table or parent pointers') before the interviewer even asked.
Top Must-Know Interview Questions & Model Answers
Q1: How do you determine whether a problem should be solved with Dynamic Programming versus Greedy versus plain Divide-and-Conquer?
- •If you can prove an exchange argument or matroid property showing the locally best choice never hurts the global optimum, Greedy is simpler and faster than DP.
- •If recursive subproblems repeat (e.g., fib(n-2) is reached via multiple paths), DP's memoization pays off; if they never repeat (merge sort's halves), plain divide-and-conquer suffices.
Q2: What is the difference between top-down memoization and bottom-up tabulation, and when would you prefer one over the other?
- •Top-down is faster to derive correctly under interview time pressure because it's a direct translation of the recursive definition plus a cache.
- •Bottom-up is generally preferred as final interview code because it avoids stack overflow risk on deep recursion and makes space optimization (rolling arrays) straightforward.
Q3: Explain the Climbing Stairs problem and how it generalizes to counting problems with a variable step size.
- •The base cases dp[0] = 1 (one way to stand at the start) and dp[1] = 1 anchor the recurrence.
- •For k possible step sizes, dp[i] = sum(dp[i-s] for s in stepSizes), and if k is large the sliding-window sum trick keeps this at O(N) instead of O(N*k).
Q4: Walk through the House Robber problem: how do you derive dp[i] = max(dp[i-1], dp[i-2] + nums[i])?
- •Because adjacent houses trigger alarms, robbing house i forbids house i-1, forcing the recurrence to reach back two steps instead of one.
- •Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]) to seed the first two positions before the general recurrence applies.
Q5: How does House Robber II handle the circular array constraint where the first and last houses are adjacent?
- •Running the O(N) linear solution twice keeps overall complexity at O(N) rather than requiring a genuinely circular DP formulation.
- •Edge case: a single-house array must be handled separately (return nums[0]) since both sub-ranges would otherwise degenerate incorrectly.
Q6: Describe an O(N log N) approach to Longest Increasing Subsequence and why it beats the O(N^2) DP.
- •The naive DP defines dp[i] = 1 + max(dp[j]) for j < i with nums[j] < nums[i], requiring O(N^2) comparisons across all pairs.
- •The patience-sorting approach never explicitly reconstructs the subsequence during the scan; tails.length at the end IS the LIS length, though reconstruction requires extra bookkeeping.
Q7: How do you set up the DP recurrence for Unique Paths on an M x N grid, and how do obstacles change it?
- •With obstacles, any blocked cell sets dp[i][j] = 0 regardless of its neighbors, and this zero propagates forward through the rest of the row/column automatically.
- •The first row/column base case must also respect obstacles: once a wall is hit along the edge, every subsequent edge cell becomes unreachable (0), not just the blocked one.
Q8: What is the core difference between 0/1 Knapsack and Unbounded Knapsack in both recurrence and implementation?
- •0/1: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt]+val); descending iteration ensures dp[w-wt] still reflects the PRIOR item's row when collapsed to 1D.
- •Unbounded: dp[w] = max(dp[w], dp[w-wt]+val); ascending iteration deliberately lets dp[w-wt] reflect an update already made in the same pass, permitting reuse.
Q9: How do you solve Partition Equal Subset Sum, and how does it reduce to 0/1 Knapsack?
- •dp[s] = true if some subset of items processed so far sums to s; transition is dp[s] = dp[s] OR dp[s - num] (again requiring descending iteration to prevent reuse).
- •This is knapsack where 'value' and 'weight' are identical (the number itself), and the 'capacity' is the target half-sum.
Q10: Explain Coin Change (minimum coins) and Coin Change II (number of combinations) — why do they need different loop orders?
- •Coin Change: dp[amount] = min(dp[amount], dp[amount-coin]+1) for every coin; initialize dp[0]=0 and all others to Infinity, answer is -1 if dp[target] remains Infinity.
- •Coin Change II: iterating coins outer and amount inner ensures each combination is counted once (order-independent); swapping the loops would count permutations (order-dependent) instead, inflating the answer.
Q11: How do you approach Matrix Chain Multiplication using interval DP, and what does dp[i][j] represent?
- •Recurrence: dp[i][j] = min over k in [i, j-1] of dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j].
- •Must iterate by increasing chain length (interval size) rather than row-major order, since dp[i][j] depends on strictly shorter sub-intervals.
Q12: Walk through Burst Balloons: why does dp[i][j] represent 'the balloon at k is the LAST one burst in (i, j)' rather than the first?
- •dp[i][j] = max over k in (i, j) of dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j], using padded boundary balloons with value 1.
- •Choosing 'first burst' instead would leave the resulting neighbors ambiguous, since removing an interior balloon first merges its former left/right neighbors in a way that's hard to express independently.
Q13: How do you solve Palindrome Partitioning II (minimum cuts) efficiently?
- •isPalindrome[i][j] = (s[i]==s[j]) AND isPalindrome[i+1][j-1], filled by increasing substring length exactly like other interval DP tables.
- •cuts[i] = min over all j <= i where s[j..i] is a palindrome of (cuts[j-1] + 1), with cuts[i] = 0 if the whole prefix s[0..i] is itself a palindrome.
Q14: Model Best Time to Buy and Sell Stock with Cooldown as a state machine. What are the states and transitions?
- •held[i] = max(held[i-1], rest[i-1] - price[i]): keep holding, or buy today from a resting state.
- •sold[i] = held[i-1] + price[i]; rest[i] = max(rest[i-1], sold[i-1]) — you can only start resting after either already resting or finishing yesterday's cooldown.
Q15: How does adding a transaction fee change the Buy/Sell Stock state machine compared to the cooldown variant?
- •held[i] = max(held[i-1], cash[i-1] - price[i]); cash[i] = max(cash[i-1], held[i-1] + price[i] - fee).
- •Subtracting the fee exactly once (conventionally at sell time) avoids double-charging across a single buy/sell round trip.
Q16: How do you generalize stock trading DP to 'at most K transactions'?
- •buy[k][i] = max(buy[k][i-1], sell[k-1][i-1] - price[i]); sell[k][i] = max(sell[k][i-1], buy[k][i-1] + price[i]).
- •When K >= N/2, the constraint is non-binding and the problem collapses to unlimited transactions (simple greedy sum of positive deltas), an important early-exit optimization.
Q17: Explain House Robber III on a binary tree: what does each recursive call return and why?
- •robThis = node.val + leftSkip + rightSkip (can't rob a node and its direct children simultaneously).
- •skipThis = max(leftRob, leftSkip) + max(rightRob, rightSkip) (each child is independently robbed or not, whichever is better).
Q18: How would you compute the Diameter of a Binary Tree using the same post-order DP aggregation idea as House Robber III?
- •The height returned upward is the 'local optimal substructure' component, while the diameter answer is a side-channel aggregate computed once per node during the same traversal.
- •This pattern — return one value upward for composition, but track a separate global best across all nodes — recurs in many tree DP problems (max path sum, longest zigzag path).
Q19: How is Longest Common Subsequence (LCS) actually a 2D grid DP / DAG shortest-path problem in disguise?
- •If A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (diagonal edge, extending a match).
- •Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (best of skipping a character from either string).
Q20: How do you compute Edit Distance (Levenshtein Distance) and how does it extend the LCS recurrence?
- •If characters match: dp[i][j] = dp[i-1][j-1] (no operation needed).
- •Otherwise: dp[i][j] = 1 + min(dp[i-1][j] [delete], dp[i][j-1] [insert], dp[i-1][j-1] [replace]).
Q21: Why can't Longest Increasing Subsequence be solved with a simple greedy scan, and what makes it a DP problem instead?
- •A counter-example: [1, 2, 5, 3, 4] — greedily extending from 5 misses the longer subsequence 1,2,3,4.
- •This failure of the greedy exchange argument is precisely the signal that overlapping/optimal-substructure DP (or the patience-sorting variant) is required.
Q22: How would you space-optimize a 2D grid DP solution like Minimum Path Sum from O(M*N) to O(N)?
- •Before overwriting dp[j], its old value still represents dp[i-1][j] (from the previous row) since it hasn't been touched yet this row.
- •dp[j-1] on the same pass already reflects the current row (i), giving exactly the dp[i][j-1] term needed — no extra buffering required.
Q23: When is it unsafe to space-optimize a DP table down to O(1) or O(N), and what's a concrete example?
- •Reconstructing the LCS string itself requires backtracking through the full 2D table, so an interviewer asking for the actual subsequence (not just its length) rules out full O(N) space optimization.
- •Interval DP tables where dp[i][j] depends on far-apart dp[i][k] and dp[k+1][j] for arbitrary k generally cannot be collapsed below O(N^2), since any interval might still be needed later.
Q24: How would you detect and reconstruct the actual optimal subset in a 0/1 Knapsack problem, not just the maximum value?
- •This backtracking only works because the full table (not the space-optimized 1D version) retains every intermediate row needed to distinguish 'included' from 'excluded' decisions.
- •The same backtracking technique generalizes to LCS/Edit Distance reconstruction and to interval DP's optimal split-point recovery.
Q25: How do you approach a DP problem where the state needs to track 'remaining budget' or 'count of operations used so far' as an extra dimension?
- •This pattern appears in 'at most K transactions' stock problems, 'at most K swaps,' and 'exactly K partitions' style questions.
- •Watch for exponential blowup: if the budget dimension can be large, check whether it can be bounded (e.g., K >= N/2 collapses to unlimited) before implementing the full table.
Q26: What is the time and space complexity of the naive recursive (non-memoized) solution to a typical DP problem like Fibonacci or Climbing Stairs, and why does memoization fix it?
- •The recursion tree without caching re-derives fib(n-2) through two separate paths (via fib(n-1) and directly), and this duplication compounds exponentially with depth.
- •A memo table (array or hash map) turns the exponential tree into a linear DAG of N distinct nodes, each computed once and reused by all callers.
Q27: How would you handle a DP problem on a tree that isn't binary (arbitrary number of children), such as maximizing value with adjacency constraints across a general tree?
- •robThis = node.val + sum(skip[child] for every child); skipThis = sum(max(rob[child], skip[child]) for every child).
- •Complexity remains O(N) total since each node and each edge is visited exactly once regardless of branching factor.
Q28: Explain the Longest Palindromic Substring problem using DP and its recurrence.
- •Track the start index and max length of the longest True cell seen while filling the table to answer the actual substring, not just whether one exists.
- •This is O(N^2) time and space; an alternative 'expand around center' approach achieves the same O(N^2) time with O(1) space by expanding outward from every possible center instead of tabulating.
Mistakes That Sink Otherwise Strong Candidates
Why it happens: Under interview time pressure, candidates feel pressure to start typing immediately to show progress.
The fix: Spend the first 2-3 minutes writing 'dp[i] represents...' as a comment before any implementation; this single sentence catches most design flaws before they become debugging sessions.
Why it happens: Both problems look nearly identical once collapsed to a single 1D array, and the loop direction is the only visible difference in code.
The fix: Before space-optimizing, explicitly ask 'can this item be reused in the same pass?' — if no, iterate capacity descending; if yes, iterate ascending.
Why it happens: Row-major iteration is the default mental model from other 2D DP problems like grids, where it happens to be correct.
The fix: For any dp[i][j] = f(dp[i][k], dp[k+1][j]) recurrence, iterate by increasing interval length (j - i) so every sub-interval is guaranteed ready before it's needed.
Why it happens: Simple tree traversals (like computing height or sum) only ever need one return value, so the pattern generalizes incorrectly by habit.
The fix: Whenever the problem has an adjacency or inclusion/exclusion constraint (can't pick a node and its parent), return a pair like [ifIncluded, ifExcluded] so the parent can combine children correctly.
Why it happens: Candidates want to demonstrate efficiency awareness early and skip the verification step.
The fix: Always get a correct, full-table (or memoized) solution working against the example first; only then discuss and apply space optimization as a clearly separate improvement step.
Why it happens: Base cases feel 'obvious' and get skipped mentally while focusing on the general recurrence.
The fix: Explicitly test dp[0] / empty-array / zero-capacity scenarios against your recurrence by hand before writing the loop that fills the rest of the table.
Why it happens: Top-down code looks clean and matches the natural recursive definition, so its stack cost is easy to overlook until N is large (e.g., N > 10,000).
The fix: If asked about very large inputs, proactively convert to bottom-up tabulation, which uses iteration instead of the call stack and avoids the depth limit entirely.
Why it happens: Coin Change (minimum coins) and Coin Change II (number of combinations) share the same unbounded-knapsack table shape, making it easy to paste the wrong aggregation operator.
The fix: Before coding, write down explicitly whether the answer aggregates via min/max (optimization) or += (counting), since this determines both the operator and often the loop nesting order.
Quick-Reference Cheat Sheet
Recommended Practice Quizzes on QuizCluster
Test your retention and prepare for timed live coding and MCQ technical screening rounds:
Arrays, Two-Pointers & Sliding Window
Sharpen the array traversal and windowing fundamentals that underpin many 1D and 2D DP state transitions.
Python Core & Data
Practice implementing memoization, tabulation, and recursion limits cleanly in Python for DP-heavy coding rounds.
Frequently Asked Questions
Is it enough to memorize the top 20 classic DP problems for interviews?
No. Interviewers frequently modify a classic problem (adding a fee, a cooldown, a K-transaction limit, or an obstacle) specifically to test whether you understand the underlying recurrence rather than a memorized solution. Focus on deriving the state and transition from first principles for each of the six DP families.
Should I always try to space-optimize my DP solution during an interview?
Mention it and implement it if time allows, but correctness first. State the full O(N) or O(N^2) space solution, verify it's correct against the example, and only then say 'I can reduce this to O(N) space since row i only depends on row i-1' and refactor if the interviewer wants to see it.
What's the fastest way to identify which DP family a new problem belongs to?
Ask: is the state a single index (1D), two indices over one or two sequences/a grid (2D), an interval that must be split (interval DP), an explicit day-by-day mode like holding/not-holding (state-machine), or a tree/graph structure (tree/graph DP)? This single question narrows the recurrence shape within seconds.
How much of a DP interview answer should be spent on complexity analysis?
Always state both time and space complexity for your initial solution and again after any space optimization — interviewers weight this heavily, especially distinguishing auxiliary space (the DP table) from input/output space.