Recognizing DP Problems
Dynamic programming applies when a problem has two properties: (1) Optimal substructure: the optimal solution to the problem contains optimal solutions to subproblems. (2) Overlapping subproblems: the same subproblems are solved multiple times in a naive recursive approach. If a recursive solution has these properties, DP memoizes or builds up the solution bottom-up. Pattern recognition: the problem asks for a count, maximum, minimum, or feasibility (can you achieve X?). The input suggests discrete choices (items, steps, characters). A decision at each step affects future options but not past choices.
Pattern 1: Linear DP (1D)
dp[i] depends only on dp[i-1] or a few previous states. Climbing Stairs: dp[i] = dp[i-1] + dp[i-2]. House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Maximum Subarray: dp[i] = max(nums[i], dp[i-1] + nums[i]) (Kadane’s algorithm). Decode Ways: dp[i] = (single digit valid ? dp[i-1] : 0) + (two digits valid ? dp[i-2] : 0). The transition is local: dp[i] is computed from a constant number of previous states. Space: O(n) for the array, often reducible to O(1) by keeping only the last k values.
Pattern 2: 2D DP (Two Sequences)
dp[i][j] represents the optimal solution for the first i elements of sequence A and first j elements of sequence B. LCS: dp[i][j] = dp[i-1][j-1]+1 if A[i]==B[j] else max(dp[i-1][j], dp[i][j-1]). Edit Distance: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) if A[i]!=B[j] else dp[i-1][j-1]. Unique Paths: dp[i][j] = dp[i-1][j] + dp[i][j-1]. The common structure: define dp[i][j] clearly, identify base cases (row 0, column 0), write the recurrence, fill the table row by row.
Pattern 3: Knapsack DP
0-1 Knapsack: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]). Each item used at most once — iterate weights in reverse for the 1D optimization. Unbounded Knapsack (Coin Change, Rod Cutting): items reusable — iterate weights forward. Partition Equal Subset Sum (LC 416): can the array be split into two equal-sum halves? = 0-1 knapsack where target = sum/2. Word Break (LC 139): unbounded knapsack on string positions — dp[i] = True if any word ends at position i and dp[i-len(word)] is True. The key: identify what the “capacity” dimension represents (weight, target sum, position).
Pattern 4: Interval DP
dp[i][j] = optimal answer for the sub-range [i, j]. Fill by increasing interval length. For each length L and start i, j=i+L-1: try all split points k. dp[i][j] = min/max over k of combine(dp[i][k], dp[k+1][j]) + cost(i,j). Matrix Chain Multiplication: dp[i][j] = min splits of multiplying matrices i through j. Burst Balloons (LC 312): dp[i][j] = max coins from bursting all balloons between i and j, k is the LAST to burst. O(n^3) time, O(n^2) space.
Pattern 5: State Machine DP
The state includes a “mode” or “phase” that changes on transitions. Best Time to Buy/Sell Stock with Cooldown (LC 309): states = HOLDING, NOT_HOLDING, COOLDOWN. Transitions: NOT_HOLDING → HOLDING (buy), HOLDING → COOLDOWN (sell), COOLDOWN → NOT_HOLDING (wait). dp[i][state] = max profit on day i in given state. The state dimension captures the machine’s history without storing the full history. Paint House (LC 256): dp[i][color] = min cost to paint houses 0..i with house i painted color. Constraint: adjacent houses can’t have the same color.
Approach for Interviews
Step 1: define the DP state clearly — what does dp[i] (or dp[i][j]) represent? Step 2: write the recurrence — how does dp[i] depend on smaller subproblems? Step 3: identify base cases (dp[0], dp[0][0], etc.). Step 4: determine fill order (left-to-right, bottom-to-top). Step 5: extract the answer (often dp[n] or max(dp)). Step 6: optimize space if possible (do we need the entire table or just the last row/value?).
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: LinkedIn Interview Guide