Dynamic Programming

Dynamic programming is the most feared and most rewarding topic in coding interviews. Every DP problem reduces to two steps: identify that the problem has optimal substructure and overlapping subproblems, then write the recurrence relation. The implementation (memoization vs. tabulation, 1D vs. 2D table) is secondary. Mastering the 'draw the recurrence first' habit separates candidates who struggle with DP from those who crack hard problems in interviews.

Recursion and memoizationArrays and 2D arraysBig-O analysisBasic graph traversalDPMemoizationTabulation1D DP2D DPInterval DPKnapsackLCSEdit DistanceBitmask DP

Core Concepts

1The two conditions for DP — optimal substructure and overlapping subproblems: a problem has OPTIMAL SUBSTRUCTURE if the optimal solution to the problem can be constructed from optimal solutions to its subproblems. Example: the shortest path from A to C through B is the shortest path from A to B plus the shortest path from B to C. A problem has OVERLAPPING SUBPROBLEMS if the same subproblem is solved multiple times in the naive recursive solution. Example: Fibonacci — fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) again. Without memoization, the recursion tree has exponential branches but only O(n) distinct subproblems. DP caches solutions to avoid redundant work, turning exponential time into polynomial time.
2Memoization (top-down DP) vs. tabulation (bottom-up DP): MEMOIZATION adds a cache (dict or array) to the naive recursive solution. You write the recursion naturally and let the cache prevent redundant calls. Advantages: only computes subproblems that are actually needed; recursion structure makes the subproblem definition explicit. Disadvantages: call stack overhead; may hit Python's recursion limit. TABULATION fills a DP table iteratively, starting from base cases. Advantages: no recursion overhead; easier to optimize space (often only need previous row/column). Disadvantages: must determine the correct iteration order (all dependencies must be computed before the current cell). For interviews: memoization is usually faster to code; tabulation is preferred for space-optimized solutions.
31D DP — the house robber pattern: in house robber (LC 198), dp[i] = maximum money robbed from houses 0..i. Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Either you rob house i (add nums[i] to best up to i-2) or you skip it (take best up to i-1). This 'either include current item or skip it' structure is the hallmark of 1D DP. The Fibonacci structure (dp[i] depends only on dp[i-1] and dp[i-2]) allows O(1) space optimization: just keep two variables. Coin change (LC 322) uses dp[i] = min coins to make amount i, with dp[i] = min(dp[i-coin]+1 for coin in coins if coin<=i). The 'complete' knapsack allows unlimited use of each coin — iterate amounts from 0 to target.
42D DP — the LCS and edit distance patterns: LONGEST COMMON SUBSEQUENCE: dp[i][j] = LCS of s1[0..i] and s2[0..j]. Recurrence: if s1[i-1]==s2[j-1]: dp[i][j] = dp[i-1][j-1]+1; else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base cases: dp[0][j] = dp[i][0] = 0 (empty string has LCS 0 with anything). EDIT DISTANCE: dp[i][j] = minimum edits to convert s1[0..i] to s2[0..j]. Recurrence: if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]; else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (delete, insert, replace). Both are O(nm) time and O(nm) space, reducible to O(min(n,m)) space by keeping only two rows.
50-1 Knapsack — the classic 2D DP: given weights and values for n items and a knapsack of capacity W, maximize value. dp[i][w] = max value using first i items with capacity w. Recurrence: if weights[i-1] > w: dp[i][w] = dp[i-1][w] (can't fit item i); else: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1]). Each item is used AT MOST ONCE — this is the '0-1' constraint. Space optimization: iterate w from W down to weights[i] when using a 1D array (avoids using item i multiple times). Contrast with unbounded knapsack (coin change): iterate w from coin upward to allow multiple uses.
6Interval DP — burst balloons: interval DP is used when the problem involves making decisions about a contiguous subarray and the cost of a decision depends on what remains. Template: dp[i][j] = optimal value for the subarray from i to j. For BURST BALLOONS (LC 312): dp[i][j] = max coins from bursting all balloons in (i,j) (exclusive). Key insight: instead of thinking 'which balloon to burst FIRST', think 'which balloon to burst LAST in range (i,j)'. Let k be the last balloon burst: dp[i][j] = max over k of (dp[i][k] + balloons[i]*balloons[k]*balloons[j] + dp[k][j]). Outer loop: length l from 2 to n. Inner loops: i from 0 to n-l, j=i+l, k from i+1 to j. O(n^3) time.
7DP on stocks — state machine approach: stock problems (LC 123, 188, 309) are best solved with a STATE MACHINE DP. Define states like (day, transactions_remaining, holding_stock). Recurrence defines transitions between states. Example LC 309 (with cooldown): states are HELD (holding stock), SOLD (just sold, in cooldown), REST (not holding, not in cooldown). REST[i] = max(REST[i-1], SOLD[i-1]); HELD[i] = max(HELD[i-1], REST[i-1]-price[i]); SOLD[i] = HELD[i-1]+price[i]. Answer = max(REST[n-1], SOLD[n-1]). The state machine approach handles cooldowns, transaction fees, and limited transactions uniformly by adding states or transition constraints.
8DP with bitmask — for small n with subset enumeration: when n is small (typically n <= 20), you can represent a subset of elements as a bitmask (integer where bit i = 1 means element i is in the subset). dp[mask] = optimal value over the subset represented by mask. Example: MINIMUM COST TO CONNECT ALL POINTS with Steiner tree, or assignment problems where dp[mask] = min cost to assign people to jobs represented by mask. Transition: for each mask, try adding one more element not in mask. 2^n states times n transitions = O(n * 2^n) time and O(2^n) space. This is exponential but feasible for n <= 20 (2^20 is approximately 10^6).
9Greedy vs DP — when does greedy work?: greedy algorithms make the locally optimal choice at each step and never reconsider. DP explores all possible choices and uses previously computed optimal subproblems. Greedy works when the 'exchange argument' holds: you can prove that swapping any two adjacent elements in a non-greedy solution with the greedy choice doesn't make it worse. Classic greedy-OK problems: activity selection (pick earliest-ending activity), coin change with standard denominations, Huffman coding. DP is needed when greedy fails: coin change with arbitrary denominations (greedy [25,20,10,5,1] for 40 gives 25+10+5 = 3 coins, but 20+20 = 2 coins). The tell: if you can give a counter-example to greedy, use DP.

Key Patterns & Templates

1D DP (bottom-up): dp=[base]*n; for i in range(start, n): dp[i] = f(dp[i-1], dp[i-2], ...); return dp[n-1]

2D DP: dp=[[0]*(m+1) for _ in range(n+1)]; fill base cases; for i in range(1,n+1): for j in range(1,m+1): dp[i][j]=...

Memoization: from functools import lru_cache; @lru_cache(maxsize=None); def dp(i, j): ... return answer

0-1 Knapsack (1D optimized): dp=[0]*(W+1); for each item: for w in range(W, weight-1, -1): dp[w]=max(dp[w], dp[w-weight]+value)

Unbounded knapsack / coin change: dp=[inf]*(amount+1); dp[0]=0; for w in range(1,amount+1): for coin: dp[w]=min(dp[w], dp[w-coin]+1)

Interval DP: for l in range(2,n+1): for i in range(n-l+1): j=i+l; for k in range(i+1,j): dp[i][j]=max(dp[i][j], f(dp[i][k],dp[k][j]))

LCS: if s[i-1]==t[j-1]: dp[i][j]=dp[i-1][j-1]+1; else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])

LIS O(n log n): tails=[]; for x in nums: pos=bisect_left(tails,x); if pos==len(tails): tails.append(x); else: tails[pos]=x; return len(tails)

Worked Examples

Given two strings word1 and word2, return the minimum number of operations (insert, delete, replace a character) to convert word1 to word2.

1Step 1 — Define the subproblem: dp[i][j] = minimum operations to convert word1[0..i-1] to word2[0..j-1]. The answer is dp[len(word1)][len(word2)].

2Step 2 — Base cases: dp[i][0] = i (delete all i characters from word1 to get empty string). dp[0][j] = j (insert j characters to get word2[0..j-1] from empty string).

3Step 3 — Recurrence: if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] (characters match — no operation needed, same cost as without these characters). Else: dp[i][j] = 1 + min(dp[i-1][j-1] (replace), dp[i-1][j] (delete from word1), dp[i][j-1] (insert into word1)).

4Step 4 — Walk through example: word1='horse', word2='ros'. Table cell [1][1]: h vs r — mismatch, min(dp[0][0],dp[0][1],dp[1][0])+1 = min(0,1,1)+1 = 1. Continue filling row by row. dp[5][3] = 3.

5Step 5 — Space optimization: each row only needs the previous row. Use two 1D arrays (prev and curr) or one 1D array filled right-to-left. Or use O(min(m,n)) space by making word2 the shorter string.

✓ Time O(nm), Space O(nm) basic, O(min(n,m)) optimized. The three transitions map directly to operations: diagonal (replace or free match), up (delete from word1), left (insert into word1). Tracing back through the table gives the actual sequence of operations. This problem is also the basis for DNA sequence alignment in bioinformatics (Needleman-Wunsch algorithm).

Common Mistakes

⚠

Confusing 0-1 knapsack with unbounded knapsack iteration order: for 0-1 knapsack (each item used at most once), iterate the weight dimension BACKWARDS (W down to weight[i]). For unbounded knapsack / coin change (items reusable), iterate weight FORWARDS. The reason: backward iteration ensures dp[w - weight[i]] refers to the state BEFORE item i was considered (i.e., item i not yet used). Forward iteration allows dp[w - coin] to already include the current coin (reuse allowed).

⚠

Forgetting to initialize the entire DP table correctly: for minimization problems, initialize dp to float('inf') (not 0) except the base case. Initializing to 0 causes incorrect answers because taking 'zero operations' to reach an impossible state is falsely valid. Conversely, for maximization (counting paths), initialize to 0. Always ask: 'what does dp[i] = 0 mean semantically? Is that the correct base case or a wrong assumption?'

⚠

Writing the memoized recursion without handling the return value correctly: a common bug is returning from the middle of the function before caching, or not returning the cached value at the top. With @lru_cache, this is automatic. Without it: always check the cache FIRST (if key in memo: return memo[key]), compute the result, STORE it (memo[key] = result), then return it. Failing to return the cached value means the cache is never used.

⚠

Interval DP: iterating over (i, j) pairs instead of interval length: interval DP requires processing shorter intervals before longer ones. Iterating i from 0 to n and j from i to n does NOT guarantee this order — when computing dp[i][j], dp[i+1][j] (a shorter interval) might not be computed yet. Always iterate by LENGTH: for l in range(2, n+1): for i in range(n-l+1): j = i + l - 1.

⚠

Applying greedy when DP is needed (or vice versa): the canonical mistake is using greedy for coin change with arbitrary denominations. Always test greedy with a counter-example. If coins are [1, 3, 4] and target is 6: greedy gives 4+1+1=3 coins but DP gives 3+3=2 coins. If you can construct a counter-example in 30 seconds, greedy is wrong — use DP. If you cannot find a counter-example, look for an exchange argument proof, then consider greedy.

Back to SWE Hub