Dynamic Programming - Dev Weekends

What is Dynamic Programming?

Dynamic Programming solves complex problems by breaking them into overlapping subproblems and storing results to avoid redundant computation. It transforms exponential solutions into polynomial ones. Think of computing Fibonacci numbers naively. fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). Notice that fib(3) is computed twice — and the redundancy explodes exponentially. DP eliminates this by storing each result the first time it is computed and reusing it for free afterward. The Fibonacci tree collapses from O(2^n) calls into O(n) lookups. Two conditions must hold for DP to apply:

Optimal substructure: The optimal solution to the problem contains optimal solutions to its subproblems. (The shortest path from A to C through B uses the shortest path from A to B.)
Overlapping subproblems: The same subproblems are solved repeatedly. (If subproblems are independent and non-overlapping, you have divide and conquer instead.)

DP comes in two flavors. Top-down (memoization): write the natural recursion and cache results. Bottom-up (tabulation): fill a table iteratively from smallest subproblems to largest. Both yield the same asymptotic complexity; bottom-up avoids recursion overhead and is easier to space-optimize.

Quick Recognition: If you see “optimal” (min/max), “number of ways”, or “can we achieve” combined with choices at each step, think DP!

LeetCode Pattern Recognition Cheatsheet — the seven DP families you must memorize:

“max / min over choices” — minimum cost path, maximum profit, longest something. Reach for DP first.
“count number of ways” — ways to climb stairs, decode strings, partition. Counting DP is dp[i] += dp[i - k] style.
“is X possible / can you achieve” — boolean DP, e.g. Partition Equal Subset Sum (LC 416), Word Break (LC 139).
Overlapping subproblems plus optimal substructure — the two textbook prerequisites. If subproblems do not overlap, it is divide-and-conquer, not DP.

Sub-categories every LeetCode grinder must know:

Family	Signature	Canonical LeetCode
1D linear DP	`dp[i]` depends on `dp[i-1]`, `dp[i-2]`, …	70 Climbing Stairs, 198 House Robber, 53 Max Subarray, 91 Decode Ways
2D grid DP	`dp[i][j]` depends on neighbors in a grid	62 Unique Paths, 64 Min Path Sum, 221 Maximal Square
0/1 knapsack	each item taken at most once; backwards capacity loop	416 Partition Equal Subset Sum, 494 Target Sum
Unbounded knapsack	each item reusable; forward capacity loop	322 Coin Change, 518 Coin Change II, 279 Perfect Squares
LCS / LIS family	two strings or one sequence, monotonic relation	1143 LCS, 300 LIS, 72 Edit Distance, 5 Longest Palindrome
Interval DP	`dp[i][j]` over a contiguous range, often O(n^3)	312 Burst Balloons, 1547 Min Cost to Cut Stick, 5 Longest Palindrome
Tree DP	post-order recursion returning a tuple of states	337 House Robber III, 124 Max Path Sum, 968 Cameras
Bitmask DP	state encodes a set, n at most around 20	691 Stickers, 847 Shortest Path Visiting All Nodes, 1125 Smallest Sufficient Team

Three-second recognition rules:

“Subarray” plus “max / min” -> Kadane (1D DP).
“Two strings” plus “longest / minimum operations” -> 2D LCS-style.
“Choose items to fit a capacity” -> knapsack (0/1 if each item once, unbounded if reusable).
“Number of distinct ways to …” -> counting DP (often coin-change shape).
Small n (at most around 20) plus “visit every X” -> bitmask DP.
Tree input plus “rob / cover / paint without conflict on edges” -> tree DP.

Pattern Recognition Checklist

Use DP When

Problem has optimal substructure
Same subproblems solved repeatedly
Need to find min/max/count
Choices at each step affect result
Can break into smaller similar problems

Don't Use When

Greedy choice works (no need to try all)
No overlapping subproblems
Need all solutions (use Backtracking)
Simple iteration is sufficient

When to Use

Optimal Substructure

Optimal solution contains optimal solutions to subproblems

Overlapping Subproblems

Same subproblems are solved multiple times

Counting Problems

Number of ways to achieve something

Optimization

Minimize/maximize under constraints

The IDEAL Framework

Identify

Recognize it’s a DP problem (optimal/count + choices + constraints)

Define

Define what dp[i] or dp[i][j] represents

Express

Write the recurrence relation (transition equation)

Analyze

Determine base cases and computation order

Look back

Optimize space if possible

Pattern Variations

1. 1D DP (Linear)

The simplest DP pattern. The state is a single index (usually position or amount), and each state depends on a constant number of previous states. Climbing Stairs: At step i, you could have arrived from step i-1 (one step) or i-2 (two steps). So dp[i] = dp[i-1] + dp[i-2] — this is Fibonacci with different base cases. Space optimization insight: Since dp[i] only depends on dp[i-1] and dp[i-2], you do not need the full array — just two variables. This reduces space from O(n) to O(1). Always look for this pattern in 1D DP. Time: O(n). Space: O(n) or O(1) optimized.

def climb_stairs(n):
    """Number of ways to climb n stairs (1 or 2 steps)"""
    if n <= 2:
        return n
    
    # STATE DEFINITION: dp[i] = number of distinct ways to reach step i
    dp = [0] * (n + 1)
    dp[1] = 1   # Base case: one way to reach step 1 (single step)
    dp[2] = 2   # Base case: two ways to reach step 2 (1+1 or 2)
    
    for i in range(3, n + 1):
        # TRANSITION: arrive from one step below OR two steps below
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

# SPACE OPTIMIZED: only keep the two most recent values
def climb_stairs_optimized(n):
    if n <= 2:
        return n
    
    prev2, prev1 = 1, 2       # dp[i-2] and dp[i-1]
    for i in range(3, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    
    return prev1

2. 2D DP (Grid/Sequence)

When the state depends on two dimensions (e.g., position in a grid, or two indices into two strings), you need a 2D DP table. Unique Paths: Count how many ways a robot can go from the top-left corner to the bottom-right corner of an m x n grid, moving only right or down. Each cell (i, j) can only be reached from (i-1, j) (above) or (i, j-1) (left), so dp[i][j] = dp[i-1][j] + dp[i][j-1]. The first row and first column are all 1s because there is only one way to reach them (straight line). Walked example: 3x3 grid. dp[0][*] = [1,1,1], dp[*][0] = [1,1,1]. dp[1][1] = dp[0][1] + dp[1][0] = 1+1 = 2. dp[1][2] = dp[0][2] + dp[1][1] = 1+2 = 3. dp[2][1] = dp[1][1] + dp[2][0] = 2+1 = 3. dp[2][2] = dp[1][2] + dp[2][1] = 3+3 = 6. Answer: 6 paths. Space optimization insight: Row i only depends on row i-1. So we can use a 1D array of size n and update it in place, left to right. dp[j] += dp[j-1] effectively computes old_dp[j] + dp[j-1] because dp[j] still holds the value from the previous row when we read it. Time: O(m * n). Space: O(m * n) or O(n) optimized.

def unique_paths(m, n):
    """Count paths from top-left to bottom-right (right/down only)"""
    # dp[i][j] = paths to reach cell (i, j)
    dp = [[1] * n for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]

# Space optimized to O(n)
def unique_paths_optimized(m, n):
    dp = [1] * n
    
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]
    
    return dp[n-1]

3. Knapsack Pattern

The 0/1 knapsack is the gateway to a huge family of DP problems. At each item, you make a binary choice: take it or skip it. This “take or skip” decision structure appears in Partition Equal Subset Sum, Target Sum, Coin Change (bounded), and many more. State: dp[i][w] = maximum value achievable using the first i items with capacity w. Transition: For each item, either skip it (dp[i-1][w]) or take it (dp[i-1][w - weight_i] + value_i). Take the max. Space optimization: Since row i only depends on row i-1, use a 1D array. The trick: iterate w backwards so that dp[w - weight_i] still reflects the previous row (not the current one). Iterating forwards accidentally allows item reuse (turning 0/1 into unbounded knapsack). Time: O(n * W). Space: O(n * W) or O(W) optimized.

def knapsack_01(weights, values, capacity):
    """Maximum value within capacity (each item once)"""
    n = len(weights)
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # OPTION 1: skip item i -- carry forward from previous row
            dp[i][w] = dp[i-1][w]
            
            # OPTION 2: take item i (if it fits)
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w], 
                              dp[i-1][w - weights[i-1]] + values[i-1])
    
    return dp[n][capacity]

# SPACE OPTIMIZED to O(W) using a single row
def knapsack_01_optimized(weights, values, capacity):
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        # CRITICAL: traverse BACKWARDS to avoid reusing the same item
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

4. LCS Pattern (Two Strings)

The Longest Common Subsequence (LCS) is the foundation for a huge family of two-string DP problems: edit distance, shortest common supersequence, and diff algorithms. State: dp[i][j] = length of the LCS of text1[:i] and text2[:j]. Transition: If the current characters match (text1[i-1] == text2[j-1]), extend the LCS from dp[i-1][j-1] + 1. Otherwise, the LCS is the better of skipping one character from either string: max(dp[i-1][j], dp[i][j-1]). Walked example: text1 = “ace”, text2 = “abcde”. Build a 4x6 table. At (1,1): ‘a’==‘a’, dp=1. At (2,3): ‘c’==‘c’, dp=2. At (3,5): ‘e’==‘e’, dp=3. LCS = “ace”, length 3. Time: O(m * n). Space: O(m * n) or O(min(m, n)) optimized (since each row depends only on the previous row).

def longest_common_subsequence(text1, text2):
    """Find LCS length of two strings"""
    m, n = len(text1), len(text2)
    # dp[i][j] = LCS of text1[:i] and text2[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

5. House Robber (Cannot Take Adjacent)

A classic “cannot take adjacent” DP problem. A robber wants to maximize stolen money, but robbing two adjacent houses triggers an alarm. State: dp[i] = maximum money obtainable from houses 0..i. Transition: At house i, you either rob it (take nums[i] plus the best from non-adjacent houses: dp[i-2] + nums[i]) or skip it (keep dp[i-1]). Take the max. Walked example: nums = [2, 7, 9, 3, 1]. dp[0]=2, dp[1]=max(2,7)=7. dp[2]=max(7, 2+9)=11. dp[3]=max(11, 7+3)=11. dp[4]=max(11, 11+1)=12. Answer: 12 (rob houses 0, 2, 4). Space optimization: Since dp[i] only depends on dp[i-1] and dp[i-2], two variables suffice — the same rolling-window trick as Climbing Stairs. Time: O(n). Space: O(n) or O(1) optimized. Common variation: House Robber II (circular) — run the algorithm twice, once excluding the first house and once excluding the last, then take the max.

def house_robber(nums):
    """Maximum sum without taking adjacent elements"""
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    # dp[i] = max money robbing houses 0..i
    # Either rob house i (dp[i-2] + nums[i]) or skip it (dp[i-1])
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    
    return dp[-1]

# Space optimized
def house_robber_optimized(nums):
    prev2, prev1 = 0, 0
    
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    
    return prev1

6. Coin Change

An unbounded knapsack variant — each coin can be used unlimited times. The key difference from 0/1 knapsack: we iterate amounts forward (reuse is intentional). State: dp[i] = minimum number of coins needed to make amount i. Transition: For each amount i, try every coin: dp[i] = min(dp[i], dp[i - coin] + 1). Edge case: If dp[amount] is still infinity, the amount cannot be formed — return -1. Walked example: coins = [1, 3, 4], amount = 6. dp = [0, 1, 2, 1, 1, 2, 2]. Answer: 2 (coins 3+3). Time: O(amount * len(coins)). Space: O(amount).

def coin_change(coins, amount):
    """Minimum coins to make amount"""
    # dp[i] = minimum number of coins to make amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0   # Base case: 0 coins needed to make amount 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != float('inf'):
                # Using this coin: 1 (this coin) + coins for the remainder
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

Classic Problems

1. Climbing Stairs

Pattern: 1D DP (Fibonacci-like)State: dp[i] = ways to reach step i

2. Longest Increasing Subsequence

Pattern: 1D DP with O(n^2) or binary search O(n log n)State: dp[i] = LIS ending at index i

3. Edit Distance

Pattern: 2D DP on two stringsState: dp[i][j] = min operations to convert s1[:i] to s2[:j]

4. Partition Equal Subset Sum

Pattern: 0/1 Knapsack variantState: dp[i][sum] = can we make sum using first i elements?

Common Mistakes

Avoid These Pitfalls:

Vague state definition: You must be able to state in one sentence what dp[i] (or dp[i][j]) represents. If you cannot, your transition will be wrong. Write the definition as a comment before coding.
Missing or wrong base cases: dp[0] = 0 for counting stairs but dp[0] = 1 for counting paths (one way to stay at the origin). Wrong base cases propagate errors to every subsequent cell.
Wrong iteration order: In 0/1 knapsack, iterating capacity forward accidentally allows item reuse. In LCS, you must fill row by row left to right. Always draw the dependency arrows before coding.
Integer overflow: Problems asking for counts modulo 10^9+7 hint that raw values overflow. Apply the modulus at every addition, not just at the end.
Returning dp[n] when you should return dp[n-1] (or vice versa): Off-by-one on the final answer. Trace a small example to verify.
Jumping to DP before brute force: In an interview, start with recursive brute force, explain overlapping subproblems, add memoization, then convert to bottom-up. This progression demonstrates your reasoning.

Debugging Checklist

When your DP solution fails:

Check State Definition

Is dp[i] clearly defined? Can you explain what it represents?

Check Base Cases

Have you initialized all necessary base cases correctly?

Check Recurrence

Does your transition cover all cases? Any edge cases missed?

Check Iteration Order

Are you computing dp[i] only after dp[i-1], dp[i-2], etc.?

Check Return Value

Are you returning the right cell? dp[n] vs dp[n-1]?

DP Pattern Categories

Category	Examples	State Definition
Linear DP	Climbing Stairs, House Robber	dp[i] = answer for first i elements
Grid DP	Unique Paths, Min Path Sum	dp[i][j] = answer reaching (i,j)
String DP	LCS, Edit Distance	dp[i][j] = answer for s1[:i], s2[:j]
Knapsack	0/1 Knapsack, Coin Change	dp[i][w] = answer using i items, capacity w
Interval DP	Matrix Chain, Burst Balloons	dp[i][j] = answer for interval [i,j]
Tree DP	House Robber III	dp[node] = answer for subtree at node

Complexity Quick Reference

Problem Type	Time	Space	Optimization
1D DP	O(n)	O(n) → O(1)	Keep only last 2 values
2D Grid DP	O(mn)	O(mn) → O(n)	Keep only previous row
String DP (LCS)	O(mn)	O(mn) → O(n)	Keep only previous row
Knapsack	O(nW)	O(nW) → O(W)	Single row iteration
Interval DP	O(n³)	O(n²)	Usually not optimizable

Interview Problems by Company

Easy
Medium
Hard

Problem	Company	DP Type
Climbing Stairs	All	1D Linear
Min Cost Climbing Stairs	Amazon	1D Linear
Maximum Subarray	All	1D (Kadane’s)
Best Time to Buy Stock	Amazon	1D State Machine
House Robber	Google, Meta	1D Linear

Problem	Company	DP Type
Unique Paths	All FAANG	2D Grid
Coin Change	Amazon, Google	Unbounded Knapsack
LCS	Microsoft, Google	2D String
Word Break	Meta, Amazon	1D with Dictionary
Longest Increasing Subseq	Google	1D + Binary Search

Problem	Company	DP Type
Edit Distance	Google	2D String
Regular Expression	Meta, Google	2D String
Burst Balloons	Google	Interval DP
Longest Valid Parens	Meta	1D Stack/DP
Interleaving String	Amazon	2D String

Interview Tips

How to Explain Your Approach

Script for interviews:

“I notice this is asking for [optimal/count], which suggests DP.”
“Let me define the state: dp[i] represents…”
“The recurrence is: dp[i] = … because…”
“Base case is dp[0] = … because…”
“Time is O(…) and space is O(…), which I can optimize to…”

When Interviewer Says...

Interviewer Says	You Should Think
”Find minimum/maximum”	Optimization DP
”Count the number of ways”	Counting DP
”Can you achieve X?”	Boolean DP (true/false)
“Optimize your recursion”	Add memoization
”Reduce space complexity”	Rolling array technique

Top-Down vs Bottom-Up

Top-Down (Memoization):

Easier to write (natural recursion)
Only computes needed subproblems
Can have stack overflow for large inputs

Bottom-Up (Tabulation):

Usually faster (no recursion overhead)
Easier to optimize space
Must compute all subproblems

Recommendation: Start with top-down, convert to bottom-up if needed.

How to Derive a DP Recurrence — The Five-Step Recipe

This is the single most important DP skill. Most failures are not “I cannot code DP,” they are “I cannot derive the recurrence.” Use these five steps every time, in this exact order:

1. Define dp[i] (or dp[i][j]) in plain English first

Write a one-sentence definition of what dp[i] means before writing any code. Example: “dp[i] = the minimum number of coins to make amount i.” If you cannot finish that sentence cleanly, you have the wrong state.

2. Write the recurrence by considering the last decision

Ask: “what was the last move that led to the answer at dp[i]?” Enumerate every possible last move. Example for Coin Change: the last coin was some c from the coin set, so dp[i] = min(dp[i - c] + 1) over all c <= i.

3. Identify the base case(s)

What is dp[0]? What about other small inputs? Coin Change: dp[0] = 0 (zero coins for amount 0). House Robber: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]). A wrong base case shifts every later value.

4. Decide the iteration order

dp[i] must be computed only after every state it depends on. For 1D DP this is usually left-to-right. For 2D DP it is row-by-row, left-to-right. For 0/1 knapsack with rolling array, capacity must iterate backwards. For interval DP, iterate by interval length, smallest first.

5. Optimize space (last, never first)

Once correct, ask: does dp[i] depend only on dp[i-1]? Then drop to two scalars. Does row i depend only on row i-1? Then drop to a 1D rolling array. Never optimize space before correctness; it makes debugging miserable.

DP Templates

Three reusable shapes covering the bulk of LeetCode DP problems.

Top-Down (Memoization)

Python

from functools import lru_cache

def solve(...):
    @lru_cache(maxsize=None)
    def f(state):
        if base_case(state):
            return base_value(state)
        best = INITIAL
        for next_state, cost in transitions(state):
            best = combine(best, f(next_state) + cost)
        return best
    return f(initial_state)

Java

Map<Long, Integer> memo = new HashMap<>();
int f(long state) {
    if (isBaseCase(state)) return baseValue(state);
    if (memo.containsKey(state)) return memo.get(state);
    int best = INITIAL;
    for (Transition t : transitions(state)) {
        best = combine(best, f(t.nextState) + t.cost);
    }
    memo.put(state, best);
    return best;
}

C++

unordered_map<long long, int> memo;
int f(long long state) {
    if (isBaseCase(state)) return baseValue(state);
    auto it = memo.find(state);
    if (it != memo.end()) return it->second;
    int best = INITIAL;
    for (auto& t : transitions(state)) {
        best = combine(best, f(t.nextState) + t.cost);
    }
    return memo[state] = best;
}

Bottom-Up Tabulation (1D)

Python

def solve(n):
    dp = [BASE] * (n + 1)
    dp[0] = ...                    # base case(s)
    for i in range(1, n + 1):
        for choice in choices(i):
            dp[i] = combine(dp[i], dp[i - choice.cost] + choice.value)
    return dp[n]

Bottom-Up Tabulation (2D)

Python

def solve(m, n):
    dp = [[BASE] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = ...                 # base case(s)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = recurrence(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

Space-Optimized 1D Rolling

Python

def solve(n):
    prev2, prev1 = BASE, BASE
    for i in range(2, n + 1):
        curr = recurrence(prev1, prev2)
        prev2, prev1 = prev1, curr
    return prev1

Space-Optimized 2D Rolling (one row)

Python

def solve(m, n):
    dp = [BASE] * (n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # dp[j] currently holds previous row's value
            dp[j] = recurrence(dp[j], dp[j - 1])   # in-place update
    return dp[n]

For 0/1 knapsack with rolling array, iterate j backwards so you read the previous row’s value before overwriting it.

Worked LeetCode Problems

Eight canonical DP problems with full state definition, recurrence derivation, and code in multiple languages. If you can write all eight from scratch in fifteen minutes each, you are senior-ready on DP.

LC 70 — Climbing Stairs (Easy, 1D linear)

Define: dp[i] = number of distinct ways to reach step i. Recurrence: to reach step i, the last move was either +1 from i - 1 or +2 from i - 2. So dp[i] = dp[i-1] + dp[i-2]. Base: dp[0] = 1 (one way to “be” at the start), dp[1] = 1.

Python

def climbStairs(n):
    if n <= 1: return 1
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

LC 198 — House Robber (Medium, 1D linear)

Define: dp[i] = max money robbed from the first i houses. Recurrence: at house i, either rob it (dp[i-2] + nums[i]) or skip it (dp[i-1]). Take the max. Base: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

Python

def rob(nums):
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
    return prev1

LC 322 — Coin Change (Medium, unbounded knapsack)

Define: dp[a] = minimum coins to make amount a. Use infinity for unreachable amounts. Recurrence: the last coin was some c from coins, so dp[a] = min(dp[a - c] + 1) over all c <= a. Base: dp[0] = 0. Iteration order: amount outer (1..amount), coins inner. Forward direction is fine because each coin is reusable (unbounded knapsack).

Python

def coinChange(coins, amount):
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] != INF:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Java

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);   // sentinel = unreachable
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Top-down version (also acceptable in interviews):

Python

from functools import lru_cache
def coinChange(coins, amount):
    @lru_cache(maxsize=None)
    def f(a):
        if a == 0: return 0
        if a < 0: return float('inf')
        return min((f(a - c) + 1 for c in coins), default=float('inf'))
    ans = f(amount)
    return -1 if ans == float('inf') else ans

LC 416 — Partition Equal Subset Sum (Medium, 0/1 knapsack)

Define: dp[s] = true if we can pick a subset summing to s using elements seen so far. Recurrence: for each new element x, dp[s] = dp[s] OR dp[s - x] for all s from total // 2 down to x. Base: dp[0] = True (empty subset). Iteration order: elements outer; sum inner backwards — this is the textbook 0/1 vs unbounded distinction. Forward iteration would let one element contribute twice.

Python

def canPartition(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for s in range(target, x - 1, -1):    # backwards!
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

LC 1143 — Longest Common Subsequence (Medium, 2D string)

Define: dp[i][j] = length of LCS of text1[:i] and text2[:j]. Recurrence: if text1[i-1] == text2[j-1], the last characters match: dp[i][j] = dp[i-1][j-1] + 1. Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base: dp[0][*] = dp[*][0] = 0 (empty string has LCS 0 with anything).

Python

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

LC 300 — Longest Increasing Subsequence (Medium, two approaches)

Approach 1 — O(n^2) DP Define: dp[i] = length of the longest increasing subsequence ending at index i. Recurrence: dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]), or 1 if no such j.

Python

def lengthOfLIS(nums):
    if not nums: return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Approach 2 — O(n log n) Patience Sorting Maintain tails[k] = the smallest possible last element of an increasing subsequence of length k + 1. For each x, binary-search for the first tails[i] >= x and replace it with x. The length of tails at the end is the LIS length.

Python

from bisect import bisect_left
def lengthOfLIS(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Why patience sorting works: tails is strictly increasing. Replacing tails[i] with a smaller value keeps future LIS opportunities open. The actual elements of tails are not the LIS itself — only the length is correct. Reconstructing the LIS requires extra parent pointers.

LC 72 — Edit Distance (Medium-Hard, 2D string)

Define: dp[i][j] = minimum operations to convert word1[:i] into word2[:j]. Recurrence: if last characters match, dp[i][j] = dp[i-1][j-1] (free). Otherwise, take the min of three operations:

Insert: dp[i][j-1] + 1
Delete: dp[i-1][j] + 1
Replace: dp[i-1][j-1] + 1

Base: dp[0][j] = j (insert j characters), dp[i][0] = i (delete i characters).

Python

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1],   # replace
                                   dp[i-1][j],     # delete
                                   dp[i][j-1])     # insert
    return dp[m][n]

LC 5 — Longest Palindromic Substring (Medium, interval DP)

Define: dp[i][j] = True if s[i..j] is a palindrome. Recurrence: dp[i][j] = (s[i] == s[j]) and (j - i < 2 OR dp[i+1][j-1]). Iteration order: by length, smallest first. Lengths 1 and 2 are base cases.

Python

def longestPalindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    for i in range(n):
        dp[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length == 2 or dp[i+1][j-1]):
                dp[i][j] = True
                if length > max_len:
                    start, max_len = i, length
    return s[start:start + max_len]

Alternative — expand around center, which is also O(n^2) but uses O(1) space and is often easier to write under pressure:

Python

def longestPalindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        return s[l+1:r]
    best = ""
    for i in range(len(s)):
        for cand in (expand(i, i), expand(i, i + 1)):
            if len(cand) > len(best): best = cand
    return best

DP traps to remember in interviews:

Forgetting to memoize a recursive solution — exponential blowup. A pure recursive Fibonacci at n equals 40 takes minutes; with @lru_cache it is microseconds. Always add the cache before timing.
Wrong base case shifts the entire table. dp[0] for “ways to make change” is 1 (one way: use no coins). dp[0] for “min coins to make change” is 0. Get it right by tracing a tiny example.
Iteration order matters — process states in valid topological order. In 2D grid DP, you must compute row i-1 before row i. In interval DP, smaller intervals before larger. Drawing the dependency arrows on paper saves time.
0/1 vs unbounded knapsack — outer/inner loop order differs. 0/1 knapsack with rolling array iterates capacity backwards; unbounded iterates forwards. This is the most common silent bug in DP interviews.
Space optimization requires careful overwrite order. When dropping from 2D to 1D, decide whether dp[j] should hold the previous row or the current row when you read it. Mistakes here are hard to debug because results “look reasonable” but are off.
Counting DP with permutations vs combinations. LC 518 (Coin Change II) puts coins outer, amount inner — this counts combinations. Reversing the loop order counts permutations, which is a different problem (LC 377 Combination Sum IV).
Off-by-one on boundaries. dp[n] vs dp[n-1] vs dp[len(s)]. Trace a tiny input through your code by hand before submitting.
Top-down with default argument types. In Python @lru_cache will not memoize lists or dicts (unhashable). Convert to tuples or use frozenset.
Negative numbers in problems that assume non-negative. Min Subarray Sum and Maximum Product Subarray both have sign-flipping subtleties. The product DP keeps both min_so_far and max_so_far because a negative times a negative is the new max.
Missing the modulo when the problem says “answer modulo 10^9 + 7.” Apply mod after every addition, not just at the return.

Three sentences to say in any DP interview:

“Let me first define dp[i] in plain English, then derive the recurrence by considering the last decision.”
“I’ll start with top-down memoization for clarity, then convert to bottom-up if you want me to optimize space.”
“Before coding, let me trace this on the example to verify my recurrence and base case.”

Curated LeetCode List

Twelve problems grouped by sub-pattern. This is the minimum viable list for FAANG-grinding. If you have not seen one, schedule it.

LC #	Problem	Difficulty	Sub-category
70	Climbing Stairs	Easy	1D linear (Fibonacci)
198	House Robber	Easy	1D linear
53	Maximum Subarray	Easy	1D Kadane’s
91	Decode Ways	Medium	1D counting
62	Unique Paths	Medium	2D grid
64	Minimum Path Sum	Medium	2D grid
322	Coin Change	Medium	Unbounded knapsack
416	Partition Equal Subset Sum	Medium	0/1 knapsack
1143	Longest Common Subsequence	Medium	2D string
300	Longest Increasing Subsequence	Medium	LIS, both O(n^2) and O(n log n)
72	Edit Distance	Hard	2D string
5	Longest Palindromic Substring	Medium	Interval DP
312	Burst Balloons	Hard	Interval DP
337	House Robber III	Medium	Tree DP
691	Stickers to Spell Word	Hard	Bitmask DP / BFS

Practice Problems

Problem	Difficulty	Link
Climbing Stairs	Easy	LeetCode 70
House Robber	Medium	LeetCode 198
Coin Change	Medium	LeetCode 322
Longest Common Subsequence	Medium	LeetCode 1143
Edit Distance	Medium	LeetCode 72

Practice Roadmap

Week 1: 1D DP

Solve: Climbing Stairs, House Robber, Max Subarray
Focus: State definition and transitions

Week 2: 2D Grid DP

Solve: Unique Paths, Min Path Sum, Triangle
Focus: Grid traversal patterns

Week 3: String DP

Solve: LCS, Edit Distance, Palindrome Substring
Focus: Two-string state definition

Week 4: Advanced

Solve: Coin Change, Knapsack, Word Break
Focus: Recognizing DP variants

Interview Tip: Start with brute force recursion, add memoization, then convert to bottom-up DP, finally optimize space.

Interview Questions

Deep-dive questions that test real understanding of Dynamic Programming, not just template memorization. Expect interviewers to push past your initial answer into state design, optimization reasoning, and edge cases.

Q1: You're given a recursive solution that's too slow. How do you determine if DP can help, and walk me through converting it step by step.

Difficulty: FoundationalWhat interviewers are really testing: Whether the candidate has a systematic framework for recognizing DP applicability and converting recursion to DP, or whether they just pattern-match problem titles to memorized solutions. This is the single most important DP skill — everything else builds on it.Strong answer:

Two conditions must hold for DP to apply: (1) Optimal substructure — the optimal solution to the problem contains optimal solutions to subproblems, and (2) Overlapping subproblems — the recursion solves the same subproblem multiple times. If you have the first but not the second (e.g., merge sort), divide-and-conquer is sufficient. If you have neither, DP will not help.
How I verify overlapping subproblems: Draw the recursion tree for a small input. If you see the same function call appearing in multiple branches, subproblems overlap. For Fibonacci, fib(3) appears twice in the tree for fib(5). For merge sort, every recursive call operates on a unique subarray — no overlap.
Conversion steps: (1) Identify the recursive function parameters that change — these become your DP state. (2) Add a memo table (HashMap or array) keyed on those parameters. Before recursing, check the table; after computing, store the result. (3) Optionally, convert to bottom-up by determining the computation order from base cases to the final answer.
The gotcha most candidates miss: Not every parameter needs to be part of the state. If a parameter is constant across all calls (like the original array), it is not part of the DP state. Only parameters that change define the subproblem space.
Complexity impact: Memoization converts the time complexity from the number of nodes in the recursion tree (often exponential) to the number of unique subproblems times the work per subproblem. For Fibonacci: from O(2^n) to O(n) unique states times O(1) work each = O(n).

# Step 1: Naive recursion (exponential)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)  # O(2^n) -- recomputes massively

# Step 2: Add memoization (top-down DP)
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]  # O(n) time, O(n) space

# Step 3: Convert to bottom-up (tabulation)
def fib_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]  # O(n) time, O(n) space

# Step 4: Optimize space
def fib_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1  # O(n) time, O(1) space

Red flag answer: “If the problem says find minimum or count ways, it’s DP.” This is a surface-level heuristic that fails for greedy problems (which also minimize) and combinatorics (which also count). The real test is overlapping subproblems, not the problem statement keywords. Another red flag: being unable to explain why memoization makes Fibonacci O(n) — saying “it caches results” without connecting that to the number of unique subproblems.Follow-ups:

Can you give me an example of a problem with optimal substructure but WITHOUT overlapping subproblems? (Answer: merge sort, binary search. These have optimal substructure but each subproblem is unique, so memoization adds no benefit — plain divide-and-conquer is the right approach.)
When would you prefer top-down (memoization) over bottom-up (tabulation), and vice versa? Give a concrete scenario for each. (Answer: top-down when only a subset of states is reachable — e.g., a sparse state space where bottom-up would waste time computing unreachable states. Bottom-up when you need space optimization via rolling arrays, or when the recursion depth would cause a stack overflow for large inputs.)

Q2: In the 0/1 Knapsack space-optimized solution, why do we iterate capacity backwards? What breaks if we go forwards?

Difficulty: IntermediateWhat interviewers are really testing: Whether the candidate truly understands the dependency structure in DP transitions, not just the code template. The backward iteration is the most commonly memorized-but-not-understood detail in knapsack problems. If you cannot explain it, you cannot adapt to variants.Strong answer:

In the 2D knapsack, dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]). Notice both options reference row i-1 — the previous item’s row. When we compress to 1D, a single dp[w] array represents the “current” row, and we need dp[w - weight[i]] to still hold the value from the previous row.
If we iterate forwards (small w to large w), then when we compute dp[w], the value dp[w - weight[i]] has ALREADY been updated in this iteration for item i. That means we are effectively reading dp[i][w - weight[i]] instead of dp[i-1][w - weight[i]]. This allows us to pick item i multiple times — which is the Unbounded Knapsack, not 0/1 Knapsack.
Iterating backwards ensures that when we read dp[w - weight[i]], it still holds the value from the previous item’s computation (row i-1). By the time we update dp[w], all cells to its left that it depends on are still from the “old” row.
This is the single key insight that separates 0/1 Knapsack from Unbounded Knapsack in the space-optimized version. Same code, different iteration direction, completely different problems solved.

# 0/1 Knapsack: iterate BACKWARDS (each item used at most once)
for i in range(len(weights)):
    for w in range(capacity, weights[i] - 1, -1):
        dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

# Unbounded Knapsack: iterate FORWARDS (items can repeat)
for i in range(len(weights)):
    for w in range(weights[i], capacity + 1):
        dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

Red flag answer: “We go backwards to avoid using an item twice” without explaining the mechanism. Why does going forwards allow reuse? If the candidate cannot trace through a small example showing that forward iteration reads an already-updated cell, they memorized the rule without understanding it. Even worse: not knowing that forward iteration solves the Unbounded Knapsack — this is a critical connection.Follow-ups:

If I now ask you to solve the Unbounded Knapsack (each item can be used unlimited times), what single change do you make? (Answer: iterate capacity forwards instead of backwards. This deliberately allows reading the current row’s values, which models reusing items.)
What about the Bounded Knapsack where each item can be used at most K times? Can you still use a 1D array? (Answer: yes, but it is trickier. You can use binary representation — decompose K copies into groups of 1, 2, 4, … copies treated as separate items. This reduces to O(n * log(K) * W) time. Alternatively, use a sliding window maximum on the 1D array, but that is more complex to implement.)

Q3: Define the DP state for Edit Distance. Why is `dp[i][j]` defined as operations on prefixes, not suffixes or substrings?

Difficulty: IntermediateWhat interviewers are really testing: Whether the candidate understands that the state definition is a design choice that affects everything — the recurrence, base cases, and whether the problem even decomposes cleanly. Strong candidates can articulate why one state definition works and another does not.Strong answer:

dp[i][j] = minimum operations to convert word1[0..i-1] to word2[0..j-1] (first i characters of word1 into first j characters of word2).
Why prefixes work: Prefixes have a natural inductive structure. Once you know how to convert word1[0..i-1] to word2[0..j-1], extending by one character gives you exactly three choices: insert (dp[i][j-1] + 1), delete (dp[i-1][j] + 1), or replace/match (dp[i-1][j-1] + 0 or 1). Each choice reduces the problem to a strictly smaller prefix pair.
Why suffixes would also work but are less natural: you could define dp[i][j] as operations on word1[i..] to word2[j..], but the base cases become dp[m][j] = n - j and dp[i][n] = m - i, and the recurrence builds from the bottom-right corner. It is mathematically equivalent but harder to think about and code correctly.
Why arbitrary substrings do NOT work: If you define dp[i][j] as the edit distance between arbitrary substrings, you have no way to decompose the problem without knowing the endpoints of the substrings. The state would need four parameters (i1, j1, i2, j2), which is O(n^2 * m^2) — far worse than O(n * m).
Base cases from the state definition: dp[0][j] = j (inserting j characters to build word2[0..j-1] from empty string), dp[i][0] = i (deleting i characters from word1[0..i-1]). These base cases fall out naturally from the prefix definition.

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    # dp[i][j] = min ops to convert word1[:i] to word2[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases: converting to/from empty string
    for i in range(m + 1):
        dp[i][0] = i  # delete all characters
    for j in range(n + 1):
        dp[0][j] = j  # insert all characters

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # characters match, no op
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete from word1
                    dp[i][j - 1],      # insert into word1
                    dp[i - 1][j - 1]   # replace
                )
    return dp[m][n]

Red flag answer: Defining the state as “the edit distance between two strings” without specifying which substrings or prefixes. Another red flag: not being able to explain what the three transitions (insert, delete, replace) correspond to physically, or confusing which index moves for which operation. If a candidate says “delete means dp[i-1][j-1]” they have the operations mixed up.Follow-ups:

How would you reconstruct the actual sequence of operations (not just the minimum count)? (Answer: backtrack through the DP table from dp[m][n]. At each cell, check which of the three transitions was chosen by comparing values. This takes O(m + n) additional time and reveals the edit script.)
Can you optimize Edit Distance to O(min(m, n)) space? What do you lose by doing so? (Answer: yes, use a rolling two-row array since each cell only depends on the current and previous row. You lose the ability to reconstruct the edit sequence — you would need to use Hirschberg’s algorithm, which combines divide-and-conquer with space-optimized DP to achieve O(min(m, n)) space AND O(mn) time while still allowing path reconstruction.)

Q4: Coin Change asks for the minimum number of coins. Coin Change II asks for the number of combinations. How does the DP formulation differ and why?

Difficulty: IntermediateWhat interviewers are really testing: Whether the candidate understands how a subtle change in what you are counting (minimum vs count, combinations vs permutations) changes the state definition, transition, and even the iteration order. This is where many candidates who memorize one version fall apart.Strong answer:

Coin Change (minimum coins): dp[amount] = minimum coins to make amount. Transition: dp[i] = min(dp[i], dp[i - coin] + 1) for each coin. We iterate amounts in the outer loop, coins in the inner loop (or vice versa — order does not matter for min).
Coin Change II (count combinations): dp[amount] = number of ways to make amount. Transition: dp[i] += dp[i - coin]. Here, iteration order is critical. To count combinations (not permutations), coins must be the OUTER loop and amounts the INNER loop. This ensures each coin denomination is considered in order, preventing counting [1, 2] and [2, 1] as different.
Why the loop order matters for counting:
- Coins outer, amounts inner: you process all amounts for coin 1, then all amounts for coin 2, etc. This enforces an ordering on coins used — you never “go back” to an earlier coin. Result: combinations.
- Amounts outer, coins inner: for each amount, you try all coins. A later coin can be followed by an earlier coin. Result: permutations.
For min/max, loop order does not matter because min and max are commutative and idempotent — regardless of the order you discover the paths, the minimum stays the same.

# Coin Change: minimum coins (loop order doesn't matter)
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

# Coin Change II: count combinations (coins MUST be outer loop)
def coin_change_2(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:               # coins outer = combinations
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    return dp[amount]

# If you swap loops: count permutations instead
def coin_permutations(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for i in range(1, amount + 1):    # amounts outer = permutations
        for coin in coins:
            if coin <= i:
                dp[i] += dp[i - coin]
    return dp[amount]

Red flag answer: Not knowing the difference between combinations and permutations in this context, or thinking loop order never matters. If a candidate writes the counting solution with amounts as the outer loop and claims it counts combinations, that is a fundamental misunderstanding. Another red flag: initializing dp[0] = 0 for the counting version (it should be dp[0] = 1 — there is one way to make amount 0, which is using no coins).Follow-ups:

What if each coin can only be used once (like 0/1 Knapsack)? How does the solution change? (Answer: iterate coins in the outer loop and amounts BACKWARDS in the inner loop — same backward trick as 0/1 Knapsack. This prevents reusing the same coin.)
The interviewer modifies the problem: “find the number of permutations that sum to target.” Now what changes? (Answer: swap the loops so amounts are outer, coins are inner. This is actually LeetCode 377 — Combination Sum IV, which despite its name counts permutations.)

Q5: Longest Increasing Subsequence has an O(n^2) DP solution and an O(n log n) solution. Explain both and when you'd choose each.

Difficulty: SeniorWhat interviewers are really testing: Whether the candidate can go beyond the standard O(n^2) DP and articulate the clever patience-sorting / binary-search optimization. More importantly, whether they understand the trade-offs and can reconstruct the actual subsequence, not just its length.Strong answer:

O(n^2) DP approach: dp[i] = length of LIS ending at index i. For each i, scan all j < i where nums[j] < nums[i] and take dp[i] = max(dp[j] + 1). Final answer is max(dp).
O(n log n) approach (patience sorting): Maintain an array tails where tails[k] = smallest tail element of all increasing subsequences of length k + 1. For each element, binary search tails to find where it fits. If it is larger than all tails, append (extends the longest subsequence). Otherwise, replace the first tail that is >= the element (this keeps tails as small as possible for future extension).
Critical insight most people miss: The tails array is NOT the LIS itself. It is always sorted, which is what enables binary search, but its contents at any point do not form a valid subsequence of the original array. To reconstruct the actual LIS, you need a separate parent-pointer array.
When to choose which:
- O(n^2): simpler to code, easier to explain, sufficient for n at most around 5000. Also easier to adapt for variants (e.g., longest non-decreasing subsequence, count of LIS, etc.).
- O(n log n): necessary when n is large (10^5 or more). But it is harder to modify for variants — for example, counting the number of LIS of maximum length is significantly more complex with the binary search approach.

# O(n^2) DP: simple, easy to extend for variants
def lis_dp(nums):
    n = len(nums)
    dp = [1] * n  # Every element is a subsequence of length 1
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# O(n log n) patience sorting with binary search
import bisect
def lis_binary_search(nums):
    tails = []
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)   # extends longest subsequence
        else:
            tails[pos] = num    # keeps tail as small as possible
    return len(tails)

Red flag answer: Claiming the tails array IS the LIS. This is a very common misconception. For input [3, 1, 4, 1, 5, 9, 2, 6], the tails array might be [1, 2, 5, 6] at the end, but the actual LIS is [1, 4, 5, 9] or [1, 4, 5, 6]. Another red flag: not knowing the O(n^2) solution exists and jumping straight to the binary search version without being able to explain the simpler DP first — interviewers prefer candidates who show progression from simple to optimized.Follow-ups:

How would you reconstruct the actual LIS (not just its length) from the O(n log n) approach? (Answer: maintain a parent array that records, for each element, the index of the previous element in its subsequence. When you place an element in tails, record its predecessor. Then backtrack from the last element of the longest chain.)
How would you find the NUMBER of distinct longest increasing subsequences? Can the O(n log n) approach handle this efficiently? (Answer: with the O(n^2) approach, maintain a count[i] alongside dp[i]. When dp[j] + 1 == dp[i], add count[j] to count[i]. With O(n log n), this requires augmenting the tails structure with Fenwick trees or segment trees — significantly more complex, O(n log n) is still achievable but the implementation difficulty jumps.)

Q6: What is interval DP and how does it differ from linear DP? Walk me through Burst Balloons or Matrix Chain Multiplication.

Difficulty: SeniorWhat interviewers are really testing: Whether the candidate can handle DP problems where the state represents a range rather than a prefix or single index. Interval DP is a distinct mental model that many candidates never develop, and it is a common Hard-level interview topic at Google and Meta.Strong answer:

Linear DP builds solutions left to right: dp[i] depends on dp[i-1], dp[i-2], etc. The subproblems are prefixes or suffixes. Interval DP builds solutions from smaller intervals to larger ones: dp[i][j] represents the answer for the range [i, j], and you try every possible split point k in between.
The key pattern: dp[i][j] = optimize over all k in [i, j] of (dp[i][k] + dp[k][j] + cost of combining). You iterate by interval length, starting from length 1 (or 2), building up to the full range.
Burst Balloons (LC 312) walkthrough:
- Reframe: instead of “which balloon to burst first,” think “which balloon to burst LAST in range [i, j].” If balloon k is burst last in [i, j], the coins gained are nums[i-1] * nums[k] * nums[j+1] (the boundaries are still intact because k is the last to go).
- dp[i][j] = max coins from bursting all balloons in range [i, j].
- Transition: dp[i][j] = max over k in [i, j] of (dp[i][k-1] + nums[i-1] * nums[k] * nums[j+1] + dp[k+1][j]).
- The non-obvious insight: thinking about the LAST element to remove rather than the first. This is because when you burst a balloon, it changes the neighbors of adjacent balloons — forward simulation is a nightmare. But if you think about which is burst last, the two sub-intervals [i, k-1] and [k+1, j] are independent.
Complexity: O(n^3) time, O(n^2) space. The triple loop: interval length, start position, and split point.

def max_coins(nums):
    # Pad with 1s at boundaries
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    # Iterate by interval length
    for length in range(1, n - 1):        # length of interval
        for i in range(1, n - length):     # start of interval
            j = i + length - 1             # end of interval
            for k in range(i, j + 1):      # last balloon to burst
                coins = nums[i - 1] * nums[k] * nums[j + 1]
                coins += dp[i][k - 1] + dp[k + 1][j]
                dp[i][j] = max(dp[i][j], coins)

    return dp[1][n - 2]

Red flag answer: Trying to simulate bursting balloons left to right or trying a greedy approach (“burst the smallest first”). Greedy fails because the order affects neighbor relationships. Another red flag: defining the state as dp[i] = “max coins after bursting balloon i” — this does not capture enough information because the answer depends on which other balloons are still present.Follow-ups:

In Matrix Chain Multiplication, the split point k determines where you “cut” the chain. How is this similar to Burst Balloons, and what is the state? (Answer: dp[i][j] = minimum multiplications to compute the product of matrices i through j. Split at k: dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j]). Same interval DP structure.)
Can interval DP be done top-down with memoization instead of bottom-up? What are the trade-offs? (Answer: yes, and for Burst Balloons specifically, top-down is often easier to write because you do not need to think about the iteration order by interval length. The trade-off is recursion depth and potential stack overflow for large n, plus slightly higher constant factor from function call overhead.)

Q7: How do you optimize the space complexity of a 2D DP solution? Walk me through the rolling array technique and when it fails.

Difficulty: IntermediateWhat interviewers are really testing: Whether the candidate can analyze dependency structures in DP tables and apply space optimization mechanically. This is a common follow-up after any 2D DP solution and separates candidates who understand the technique from those who just memorize the optimized version.Strong answer:

The core principle: Look at which rows (or columns) each cell depends on. If dp[i][j] only depends on row i and row i-1, you only need two rows at any time — a “current” and a “previous” row. This reduces O(mn) space to O(n).
Rolling array technique: Use dp[i % 2][j] instead of dp[i][j]. Row 0 and row 1 alternate as “current” and “previous.” After processing row i, row i-2 is no longer needed and can be overwritten.
Single-row optimization (even better): In some problems like Unique Paths, you can use a single 1D array where dp[j] represents the current row being built. When you update dp[j] += dp[j-1], the dp[j] on the right side still holds the value from the previous row (which is the “up” neighbor), and dp[j-1] has already been updated to the current row (which is the “left” neighbor). This works because the dependency is only on dp[i-1][j] and dp[i][j-1].
When it FAILS:
1. When the cell depends on more than two rows (e.g., dp[i][j] depends on dp[i-1], dp[i-2], etc.). You need to keep more rows.
2. When you need to reconstruct the solution path (not just the optimal value). Space optimization destroys the full table, so you cannot backtrack. You would need Hirschberg’s divide-and-conquer trick to get both O(n) space and path reconstruction.
3. Interval DP: dp[i][j] depends on arbitrary sub-intervals, not just adjacent rows. Rolling arrays do not help here.

# Before: O(mn) space
def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

# After: O(n) space -- single row
def unique_paths_optimized(m, n):
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]  # dp[j] (old) = up, dp[j-1] (new) = left
    return dp[n-1]

# Rolling array for LCS (when you might need two explicit rows)
def lcs_rolling(text1, text2):
    m, n = len(text1), len(text2)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev, curr = curr, [0] * (n + 1)
    return prev[n]

Red flag answer: “Just use two rows instead of a full table.” This is the right idea but not enough — the interviewer wants to hear you explain WHY two rows suffice (the dependency analysis) and WHEN it does not work. Another red flag: applying the optimization incorrectly by not resetting the current row or by confusing which values are “old” vs “new” in a single-row approach.Follow-ups:

In the LCS space optimization with a single row, you need a temporary variable to hold dp[j-1] from the previous row before it gets overwritten. Walk me through why. (Answer: when computing dp[j], you need prev[j-1] — the diagonal. But dp[j-1] has already been overwritten to the current row’s value. You need to save it in a temp variable before the update. The two-row approach avoids this complexity.)
If your interviewer says “I also need the actual LCS string, not just the length, but still in O(n) space” — what do you do? (Answer: Hirschberg’s algorithm. Divide the first string in half. Use forward DP on the first half and backward DP on the second half to find the optimal split point in the second string. Recurse on each half. Total: O(mn) time, O(n) space, and you get the full path.)

Q8: Explain how the state machine DP approach works for Best Time to Buy and Sell Stock with Cooldown.

Difficulty: SeniorWhat interviewers are really testing: Whether the candidate can model a DP problem as state transitions (a finite state machine) rather than trying to force it into a simpler 1D/2D mold. State machine DP is the cleanest framework for stock problems and tests sophisticated DP thinking.Strong answer:

The mental model: On each day, you are in one of three states: held (own a stock), sold (just sold today, in cooldown tomorrow), rest (not holding and not in cooldown). The DP tracks the maximum profit in each state on each day.
Transitions:
- held[i] = max(held[i-1], rest[i-1] - prices[i]) — either keep holding, or buy today (can only buy from rest state, not sold/cooldown state).
- sold[i] = held[i-1] + prices[i] — sell what you are holding.
- rest[i] = max(rest[i-1], sold[i-1]) — either keep resting, or transition from cooldown (sold yesterday, forced to rest today).
Base cases: held[0] = -prices[0], sold[0] = 0, rest[0] = 0.
Answer: max(sold[n-1], rest[n-1]) — you should not end holding a stock.
Why state machine is powerful: The same framework handles all stock variants. No cooldown? Remove the rest state. Transaction limit K? Add a transaction counter to the state. Transaction fee? Subtract fee in the sell transition. The framework is modular.

def max_profit_cooldown(prices):
    if not prices:
        return 0

    n = len(prices)
    held = [0] * n
    sold = [0] * n
    rest = [0] * n

    held[0] = -prices[0]
    sold[0] = 0
    rest[0] = 0

    for i in range(1, n):
        held[i] = max(held[i-1], rest[i-1] - prices[i])
        sold[i] = held[i-1] + prices[i]
        rest[i] = max(rest[i-1], sold[i-1])

    return max(sold[n-1], rest[n-1])

# Space optimized to O(1):
def max_profit_cooldown_optimized(prices):
    if not prices:
        return 0
    held, sold, rest = -prices[0], 0, 0
    for i in range(1, len(prices)):
        new_held = max(held, rest - prices[i])
        new_sold = held + prices[i]
        new_rest = max(rest, sold)
        held, sold, rest = new_held, new_sold, new_rest
    return max(sold, rest)

Red flag answer: Trying to solve this with a single dp[i] = max profit on day i without tracking whether you are holding a stock. This collapses the state space and makes transitions impossible to define correctly. Another red flag: not realizing that the cooldown constraint means you cannot buy the day after selling, and trying to handle it with ad-hoc conditionals instead of clean state separation.Follow-ups:

How would you extend this to the “at most K transactions” variant (LC 188)? What changes in the state? (Answer: add a transaction counter: held[i][k] and rest[i][k]. Buying starts a new transaction, so held[i][k] = max(held[i-1][k], rest[i-1][k-1] - prices[i]). This is O(nK) time and can be optimized to O(K) space. When K >= n/2, it degenerates to the unlimited-transactions case.)
Can you draw the state machine diagram for the “with cooldown” variant and prove there are no missing transitions? (Answer: three states, five edges. rest -> held (buy), held -> held (hold), held -> sold (sell), sold -> rest (forced cooldown), rest -> rest (wait). No edge from sold -> held or sold -> sold — that is the cooldown constraint.)

Q9: What is the difference between top-down and bottom-up DP? When does one fail but the other succeed?

Difficulty: FoundationalWhat interviewers are really testing: This seems like a softball question, but the real test is whether the candidate knows the practical differences that affect production code — stack overflow risk, cache performance, space optimization feasibility — not just the textbook “one uses recursion and the other uses loops” answer.Strong answer:

Top-down (memoization): Write the natural recursion, add a cache. You solve only the subproblems that are actually needed (lazy evaluation). Pros: (1) easier to write since you think recursively, (2) skips unreachable states automatically. Cons: (1) recursion overhead and stack depth limit — Python defaults to 1000 frames, and even Java/C++ can overflow for large inputs, (2) harder to optimize space, (3) HashMap-based memo has higher constant factor than array access.
Bottom-up (tabulation): Fill a table iteratively from base cases to the answer. You must compute ALL subproblems in the right order. Pros: (1) no recursion overhead, (2) enables rolling-array space optimization, (3) better cache locality since you iterate sequentially through memory. Cons: (1) you must figure out the correct iteration order, (2) may compute states that are never needed.
When top-down succeeds but bottom-up is painful: Sparse state spaces. If your state is dp[i][j][k] where only a small fraction of (i, j, k) triples are reachable, top-down with a HashMap only visits those states. Bottom-up would allocate and iterate through the full 3D array.
When bottom-up succeeds but top-down fails: Large input sizes where recursion depth exceeds the stack limit. For example, a DP with n = 10^6 states would crash with a stack overflow in top-down Python. Bottom-up iterates without any stack concern.
In interviews, my strategy: Start with top-down (easier to get correct), then convert to bottom-up if the interviewer asks for space optimization or if the input size is large.

# Top-down: natural but stack-limited
from functools import lru_cache

def coin_change_topdown(coins, amount):
    @lru_cache(maxsize=None)
    def dp(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        return 1 + min(dp(remaining - c) for c in coins)
    result = dp(amount)
    return result if result != float('inf') else -1

# Bottom-up: iterative, space-optimizable, no stack risk
def coin_change_bottomup(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Red flag answer: “Top-down uses recursion, bottom-up uses loops.” This is technically correct but shows zero depth. If the candidate cannot discuss stack overflow, cache performance, space optimization feasibility, or sparse vs dense state spaces, they have not used DP seriously. Another red flag: claiming one is always better than the other without discussing trade-offs.Follow-ups:

In Python, how would you handle a top-down DP with n = 500,000 states? (Answer: increase the recursion limit with sys.setrecursionlimit, but this risks crashing the process. The real answer is to convert to bottom-up. Alternatively, use iterative DFS with an explicit stack to simulate the recursion.)
Can you think of a problem where top-down is asymptotically faster than bottom-up? (Answer: yes — when the state space is sparse and only a fraction of states are reachable. For example, in a DP over a grid with obstacles where most cells are blocked, top-down only visits reachable cells while bottom-up processes the entire grid.)

Q10: Walk me through how you'd solve Word Break: given a string and a dictionary, determine if the string can be segmented into dictionary words.

Difficulty: IntermediateWhat interviewers are really testing: Word Break is a canonical DP problem that tests multiple skills simultaneously: recognizing the DP structure (it looks like it could be backtracking), defining the right state, handling string manipulation efficiently, and discussing the time complexity precisely. It is one of the most frequently asked DP problems at Meta and Amazon.Strong answer:

State: dp[i] = True if the substring s[0..i-1] (first i characters) can be segmented into dictionary words. The answer is dp[n].
Transition: dp[i] is True if there exists some j < i such that dp[j] is True AND s[j..i-1] is in the dictionary. In other words, we can segmented up to position j, and the remainder from j to i is a valid word.
Base case: dp[0] = True (the empty string is trivially segmentable).
Optimization: Convert the dictionary to a HashSet for O(1) lookups. Also, you can limit the inner loop: instead of checking all j from 0 to i-1, only check positions where i - j is at most the length of the longest dictionary word. This prunes significantly.
Complexity: O(n^2 * L) where n is the string length and L is the average word length (for substring creation and hash comparison). With the max-word-length optimization, it becomes O(n * maxLen * L) in practice.
Why not backtracking? Pure backtracking without memoization is exponential. Consider the string “aaaaab” with dictionary ["a", "aa", "aaa", ...] — every partition of the prefix is valid but the string ultimately cannot be segmented (no word ends with “b”). Backtracking explores exponentially many dead ends. DP avoids this by caching results.

def word_break(s, word_dict):
    word_set = set(word_dict)
    max_len = max(len(w) for w in word_set) if word_set else 0
    n = len(s)

    dp = [False] * (n + 1)
    dp[0] = True  # empty string is segmentable

    for i in range(1, n + 1):
        for j in range(max(0, i - max_len), i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break  # no need to check further once True

    return dp[n]

Red flag answer: Using a brute-force recursive approach without memoization and not recognizing the exponential blowup. Another red flag: defining the state as dp[i] = “whether the substring starting at i can be segmented” without being able to code it correctly (confusing 0-indexed vs 1-indexed boundaries is extremely common here). Also watch for candidates who use a Trie for the dictionary but cannot explain what advantage it provides over a HashSet — a Trie helps when you are checking many prefixes from the same starting position, but for Word Break, a HashSet with the max-length optimization is usually simpler and sufficient.Follow-ups:

How would you modify this to return ALL possible segmentations (Word Break II, LC 140)? Does the DP approach still work? (Answer: use top-down DP with backtracking to reconstruct all paths. The key is that the number of valid segmentations can be exponential — e.g., “aaa” with dictionary ["a", "aa", "aaa"] has 4 segmentations — so the output itself is exponential. Memoize the list of valid segmentations from each starting position.)
What if the dictionary is extremely large (millions of words) but the input string is short (length 100)? Does your approach change? (Answer: no, because we only look up substrings of the input in the dictionary. The number of lookups is O(n * maxLen), independent of dictionary size. The HashSet lookup is O(L) where L is the substring length, not affected by dictionary size.)

Interview Deep-Dive

How do you identify that a problem requires DP rather than greedy or backtracking? Walk through your decision framework on an unfamiliar problem.

Strong Answer:

Step 1 — Check for optimal substructure. Does the optimal solution contain optimal solutions to subproblems? If not, neither greedy nor DP applies.
Step 2 — Check for overlapping subproblems. Are the same subproblems solved multiple times? If yes, DP. If subproblems are independent, D&C. If locally optimal choices suffice, greedy.
Step 3 — Try to break greedy. Spend 2-3 minutes constructing a counterexample. For coin change with coins [1, 3, 4] and target 6: greedy picks 4+1+1=3 coins, but optimal is 3+3=2. Greedy fails, so DP is needed.
Step 4 — Define the state. Articulate what dp[i] or dp[i][j] represents. If you cannot cleanly define the state, you may need a different formulation.
Key signals for DP: “minimum cost,” “maximum profit,” “number of ways,” “can you achieve X” with choices at each step.
Key signals against DP: “generate all solutions” (backtracking), “single irrevocable choice per step” (greedy), “no overlapping subproblems” (D&C).

Follow-up: In the Coin Change problem, the loop order does not matter for minimum. But in Coin Change II (counting), coins must be the outer loop. Why?

For min/max, the function is commutative and idempotent — order does not affect the result. For counting, processing amounts before coins allows [1,2] and [2,1] to be counted separately (permutations). Processing coins first enforces an ordering, counting only combinations.

Explain the rolling array space optimization for 2D DP. When does it work, when does it fail, and what do you lose?

Strong Answer:

When it works: When dp[i][j] depends only on row i and row i-1. Keep two rows and alternate. Reduces O(mn) space to O(n).
Single-row optimization: For Unique Paths, dp[j] += dp[j-1] works because dp[j] on the right still holds the previous row’s value and dp[j-1] is already updated to the current row.
When it fails: (1) Cell depends on more than two rows. (2) Interval DP — dependencies span arbitrary sub-intervals. (3) Path reconstruction needed — rolling arrays destroy the full table.
What you lose: The ability to backtrack through the table. For “just the value” problems, no loss. For “print the actual path,” use Hirschberg’s algorithm (D&C + rolling array) for O(n) space with reconstruction.
0/1 Knapsack subtlety: Iterate the inner loop backwards. Forward iteration reuses updated cells, turning 0/1 into unbounded knapsack.

Follow-up: In the LCS single-row optimization, why do you need a temporary variable?

When computing dp[j], you need the diagonal value from the previous row (old dp[j-1]). But dp[j-1] was already overwritten. Save old dp[j] in a temp variable before updating — it becomes the next iteration’s diagonal.

Compare top-down memoization versus bottom-up tabulation. When does each shine, and when does it fail?

Strong Answer:

Top-down: Easier to write (add cache to recursion). Only computes reachable states. Natural for tree DP. Fails on deep recursion (Python limit ~1000). HashMap memo has higher constant factor than array access.
Bottom-up: No recursion overhead. Better cache locality. Enables rolling-array optimization. Must figure out iteration order. Computes ALL states, even unreachable ones.
Top-down shines: Sparse state spaces (bitmask DP), tree problems, quick prototyping.
Bottom-up shines: Dense state spaces (grid/string DP), large inputs, space optimization needed.
Interview strategy: Start top-down (faster to code correctly), convert to bottom-up if asked for optimization.

Follow-up: When is top-down asymptotically faster than bottom-up?

When the state space is sparse. A grid DP with 90% blocked cells: top-down visits only reachable cells (10% of grid), while bottom-up processes everything. The asymptotic difference can be significant.

The state machine DP approach models stock trading. How does adding cooldown, transaction limits, or fees change the transitions?

Strong Answer:

Base (unlimited transactions): States: held, rest. held[i] = max(held[i-1], rest[i-1] - price), rest[i] = max(rest[i-1], held[i-1] + price).
With cooldown: Add sold state. sold[i] = held[i-1] + price, rest[i] = max(rest[i-1], sold[i-1]), held[i] = max(held[i-1], rest[i-1] - price). Cooldown prevents held from transitioning from sold — must go through rest.
With K transactions: Add counter: held[i][k], rest[i][k]. Buying starts transaction k. Time: O(nK). When K >= n/2, constraint is lifted.
With fee: Subtract fee on sell: rest[i] = max(rest[i-1], held[i-1] + price - fee).
Why state machine works: Each variant adds or modifies one state/transition. The framework is modular.
Space: All variants optimize to O(1) or O(K) since each day depends only on the previous day.

Follow-up: Draw the state machine for the cooldown variant and verify all transitions are covered.

Three states, five edges: rest->held (buy), held->held (hold), held->sold (sell), sold->rest (forced cooldown), rest->rest (wait). No edge from sold->held or sold->sold — that is the cooldown.

LeetCode Interview Q&A

Five LeetCode-grinder-flavored DP questions you should be able to answer cold. Each one comes with a strong-answer framework, full code (top-down and bottom-up where relevant), senior follow-ups, common wrong answers, and further reading.

Q1: Coin Change (LC 322) -- explain top-down and bottom-up approaches and their trade-offs.

Strong Answer Framework

Define state: dp[a] = minimum coins to make amount a.
Recurrence: the last coin used was some c, so dp[a] = min(dp[a - c] + 1) over all c at most a.
Base case: dp[0] = 0. Sentinel: infinity (or amount + 1) for unreachable.
Iteration order: amount outer (1..amount), coins inner. Forward direction works because each coin is reusable.
Both top-down and bottom-up are O(amount * coins) time and O(amount) space.

Real LeetCode Walkthrough — LC 322Top-down (memoization):

Python

from functools import lru_cache
def coinChange(coins, amount):
    @lru_cache(maxsize=None)
    def f(a):
        if a == 0: return 0
        if a < 0: return float('inf')
        return min((f(a - c) + 1 for c in coins), default=float('inf'))
    ans = f(amount)
    return -1 if ans == float('inf') else ans

Bottom-up (tabulation):

Python

def coinChange(coins, amount):
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] != INF:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Trace coins = [1, 2, 5], amount = 11: dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]. Answer: 3 (5+5+1).

Senior follow-up 1: Can you reconstruct the actual coins, not just the count?Maintain parent[a] = c alongside dp[a], recording which coin gave the best result. To reconstruct, start at amount, repeatedly subtract parent[a] and prepend it. Adds O(amount) extra space.

Senior follow-up 2: What changes for Coin Change II (number of ways) — LC 518?The recurrence flips to addition: dp[a] += dp[a - c]. Critically, the loop order changes: coins outer, amount inner. With amount outer, you would count permutations (every ordering of the same coin set), which is LC 377 — a different problem. The sub-pattern: “combinations: outer item; permutations: outer position.”

Senior follow-up 3: What if the coins can be negative?The DP breaks because dp[a - c] can require unboundedly large amounts (e.g., to reach a = 5 you could go through a = 1000 first if you have a -995 coin). The problem becomes ill-posed without an upper bound. With a bound, it becomes shortest-path on a graph — solve with BFS or Dijkstra.

Common Wrong Answers

Greedy “always pick the largest coin.” Fails on coins = [1, 3, 4], amount = 6 (greedy says 3, optimal is 2).
Top-down without memoization. Exponential, times out.
Forgetting to return -1 for unreachable amounts (sentinel handling).
Confusing LC 322 (minimum count) with LC 518 (number of ways) — different recurrences.

Further Reading

LC 518 — Coin Change II (counting variant)
LC 377 — Combination Sum IV (permutations variant)
LC 983 — Minimum Cost For Tickets

Q2: Longest Increasing Subsequence (LC 300) -- give both O(n^2) DP and O(n log n) patience sorting.

Strong Answer Framework

Start with the natural O(n^2) DP: dp[i] = length of LIS ending at index i. Recurrence: dp[i] = 1 + max(dp[j]) over j < i with nums[j] < nums[i].
Show that the answer is max(dp), not dp[n - 1] — the LIS does not have to end at the last element.
For the O(n log n) version, introduce patience sorting: maintain tails[k] = smallest possible last element of an increasing subsequence of length k + 1. For each x, binary-search and replace.
Length of tails at the end equals LIS length. Note: tails is not the LIS itself.

Real LeetCode Walkthrough — LC 300O(n^2) DP:

Python

def lengthOfLIS(nums):
    if not nums: return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

O(n log n) Patience Sorting:

Python

from bisect import bisect_left
def lengthOfLIS(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Trace nums = [10, 9, 2, 5, 3, 7, 101, 18]:

10 -> tails = [10]
9 -> tails = [9]
2 -> tails = [2]
5 -> tails = [2, 5]
3 -> tails = [2, 3]
7 -> tails = [2, 3, 7]
101 -> tails = [2, 3, 7, 101]
18 -> tails = [2, 3, 7, 18]

Answer: 4. The actual LIS could be [2, 3, 7, 18] or [2, 3, 7, 101] — the tails array does not literally hold the LIS, only the length.

Senior follow-up 1: Use bisect_left vs bisect_right — when does it matter?bisect_left for strictly increasing (LIS); bisect_right for non-decreasing (longest non-decreasing subsequence). Confusing them silently produces the wrong answer on inputs with equal elements. LC 300 wants strictly increasing, so bisect_left is correct.

Senior follow-up 2: Can you reconstruct the actual LIS, not just its length?Yes, but you need parent pointers. For each x, record the index of the predecessor (the element at tails[i - 1] at the time x was inserted). Walk backwards from the last inserted element. Adds O(n) space.

Senior follow-up 3: How does this generalize to the Longest Increasing Subsequence with at-most-K elements removed?Add a dimension: dp[i][k] = LIS ending at i using at most k removals. Recurrence considers two cases per j < i: keep j (require nums[j] < nums[i]) or remove j (just inherit dp[j-1][k-1]). O(n^2 * K) time.

Common Wrong Answers

Returning dp[n - 1] instead of max(dp) — common off-by-one trap.
Using bisect_right for strict increase — wrong for inputs with duplicates.
Trying to make the patience sorting array hold the actual LIS — it does not; it only tracks length.
Recursive without memoization — exponential.

Further Reading

LC 354 — Russian Doll Envelopes (2D LIS, sort then 1D LIS)
LC 673 — Number of Longest Increasing Subsequences
LC 1671 — Min Removals to Make Mountain Array

Q3: Edit Distance (LC 72) -- derive the recurrence from first principles.

Strong Answer Framework

Define: dp[i][j] = minimum operations to convert word1[:i] to word2[:j].
Reason about the last operation. Three possibilities (plus a free case):
- Free: if word1[i-1] == word2[j-1], last characters match, no cost: dp[i][j] = dp[i-1][j-1].
- Replace: change word1[i-1] to word2[j-1]: dp[i-1][j-1] + 1.
- Delete: drop word1[i-1]: dp[i-1][j] + 1.
- Insert: insert word2[j-1] at the end of word1[:i]: dp[i][j-1] + 1.
Base cases: dp[0][j] = j (insert j chars from empty), dp[i][0] = i (delete all i chars).
Iteration order: row by row, left to right. Each cell depends on three already-computed cells.
Complexity: O(m * n) time and space; can drop to O(min(m, n)) space with rolling rows.

Real LeetCode Walkthrough — LC 72

Python

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1],   # replace
                                   dp[i-1][j],     # delete
                                   dp[i][j-1])     # insert
    return dp[m][n]

Trace word1 = "horse", word2 = "ros". Final dp[5][3] = 3. Path: horse -> rorse (replace h with r) -> rose (delete r) -> ros (delete e). Three ops.

Senior follow-up 1: Can you do it in O(min(m, n)) space?Yes — each row depends only on the previous row, so two rolling rows suffice. Watch out: when computing dp[i][j], you need the previous row’s dp[i-1][j-1], but if you update in place left-to-right with one row, you have already overwritten that cell. Cache it in a temp variable before overwriting.

Senior follow-up 2: What if the cost of insert, delete, and replace differ (say, insert = 1, delete = 2, replace = 3)?The recurrence still has the same shape; just multiply each term by its cost: dp[i][j] = min(dp[i-1][j-1] + replace_cost, dp[i-1][j] + delete_cost, dp[i][j-1] + insert_cost). The structure is unchanged because each operation still moves you one cell in the grid.

Senior follow-up 3: How do you reconstruct the actual sequence of edits?Walk backwards from dp[m][n]. At each cell, look at which neighbor produced the minimum and record the operation. Stop when both indices reach 0. O(m + n) time, O(1) extra (besides the table).

Common Wrong Answers

Forgetting the “free” case when characters match — doubles the answer.
Wrong base case (dp[0][0] = 1 or similar). Empty-to-empty is 0 ops, not 1.
Using only two operations (replace and one of insert/delete) — gives a wrong but plausible answer.

Further Reading

LC 583 — Delete Operations for Two Strings (only delete allowed)
LC 712 — Minimum ASCII Delete Sum
LC 1143 — Longest Common Subsequence (related but simpler)

Q4: 0/1 Knapsack -- show why iteration order of capacity matters when using a 1D array.

Strong Answer Framework

State the 2D version first: dp[i][w] = max value using items 0..i-1 with capacity w.
Recurrence: take or skip item i-1. dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1]) if it fits.
Observe that row i depends only on row i-1. So compress to 1D.
Critical: when iterating with the 1D array, capacity must go backwards from W down to weight[i-1]. Forward iteration would use the current row’s dp[w - weight[i-1]], which already includes item i-1, accidentally allowing it twice — turning 0/1 into unbounded knapsack.
Walk through a tiny example to demonstrate the bug and the fix.

Real Code — 0/1 Knapsack

Python

def knapsack01(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for w in range(W, weights[i] - 1, -1):    # backwards!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

Walked example showing the bug: weights = [2], values = [3], W = 4.With backwards iteration: dp starts [0, 0, 0, 0, 0]. Item 0 (w=2, v=3):

w=4: dp[4] = max(0, dp[2] + 3) = max(0, 0 + 3) = 3.
w=3: dp[3] = max(0, dp[1] + 3) = max(0, 0 + 3) = 3.
w=2: dp[2] = max(0, dp[0] + 3) = max(0, 0 + 3) = 3.
Final dp = [0, 0, 3, 3, 3]. Answer dp[4] = 3. Correct.

With forwards iteration (the bug): dp starts [0, 0, 0, 0, 0]. Item 0:

w=2: dp[2] = max(0, dp[0] + 3) = 3.
w=3: dp[3] = max(0, dp[1] + 3) = 3.
w=4: dp[4] = max(0, dp[2] + 3) = 6. Wrong! Item used twice.
Final dp[4] = 6. This is the unbounded answer, not 0/1.

For unbounded knapsack (LC 322 Coin Change family), forward iteration is correct — it gives you item reuse for free.

Senior follow-up 1: Why does the 2D version not have this issue?Because dp[i][*] is a separate row from dp[i-1][*]. The recurrence reads only from row i-1, never from row i mid-update. The bug emerges only when you compress rows.

Senior follow-up 2: Show how the same template solves Partition Equal Subset Sum (LC 416).Same code, but the values become 1s (we just track “achievable sum” as a boolean) and the target is total // 2. The 0/1 backward-iteration discipline is identical:

dp = [False] * (target + 1)
dp[0] = True
for x in nums:
    for s in range(target, x - 1, -1):    # backwards
        dp[s] = dp[s] or dp[s - x]
return dp[target]

Senior follow-up 3: How do you reconstruct which items were taken?Use the 2D table and walk backwards from dp[n][W]. If dp[i][w] != dp[i-1][w], item i-1 was taken; subtract its weight and continue. The 1D rolling-array version loses this information — you trade space for traceability.

Common Wrong Answers

Forward iteration on the 1D array — silently solves the wrong problem.
Using a 2D array but reading from the current row instead of the previous — same bug, harder to spot.
Running greedy by value-per-weight ratio — works for fractional knapsack, not 0/1.
Forgetting the weights[i] - 1 lower bound — attempts to access negative indices.

Further Reading

LC 416 — Partition Equal Subset Sum
LC 494 — Target Sum (0/1 with sign decisions)
LC 1049 — Last Stone Weight II (0/1 in disguise)

Q5: Longest Palindromic Substring (LC 5) -- contrast interval DP and expand-around-center.

Strong Answer Framework

Define DP state: dp[i][j] = True iff s[i..j] is a palindrome.
Recurrence: dp[i][j] = (s[i] == s[j]) AND (j - i < 2 OR dp[i+1][j-1]).
Iteration order: by length, smallest first. Inside each length, slide i from 0 to n - length.
Both DP and expand-around-center are O(n^2). DP uses O(n^2) space; expand uses O(1).
For the truly optimal O(n) algorithm, mention Manacher — usually not required to code in interviews, but knowing the name signals depth.

Real LeetCode Walkthrough — LC 5Interval DP version:

Python

def longestPalindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    for i in range(n):
        dp[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length == 2 or dp[i+1][j-1]):
                dp[i][j] = True
                if length > max_len:
                    start, max_len = i, length
    return s[start:start + max_len]

Expand-around-center version (often easier to write under pressure):

Python

def longestPalindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        return s[l + 1:r]
    best = ""
    for i in range(len(s)):
        for cand in (expand(i, i), expand(i, i + 1)):
            if len(cand) > len(best): best = cand
    return best

Trace s = "babad": expand-around-center gives “bab” (or “aba” — both valid). DP version fills the table from length 1 up to 5; same answer.

Senior follow-up 1: Can you do it in O(n) time?Yes — Manacher’s algorithm. It exploits palindrome symmetry to skip redundant comparisons. Implementation is tricky (involves a “transformed” string with sentinel characters between every pair of original characters), so most interviewers will accept the O(n^2) solution unless they explicitly ask for the optimum.

Senior follow-up 2: How do you count all palindromic substrings (LC 647)?Same expand-around-center loop, but instead of tracking the longest, increment a counter every time the expand loop runs at least one iteration. O(n^2) time, O(1) space.

Senior follow-up 3: What about the Longest Palindromic Subsequence (LC 516) — not substring?Different problem: characters need not be contiguous. State: dp[i][j] = LPS of s[i..j]. Recurrence: if s[i] == s[j] then dp[i+1][j-1] + 2, else max(dp[i+1][j], dp[i][j-1]). This is essentially LCS of s and reverse(s).

Common Wrong Answers

Iterating the DP table by i outer and j inner — you would access dp[i+1][j-1] before computing it. Iteration order must be by length or by diagonal.
Returning just the length when the problem asks for the substring.
Confusing substring (contiguous) with subsequence (LC 516, non-contiguous).
Using brute force O(n^3) — check every substring with a palindrome test. Times out on n = 1000.

Further Reading

LC 516 — Longest Palindromic Subsequence
LC 647 — Palindromic Substrings (count)
LC 132 — Palindrome Partitioning II (DP plus interval)

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

Documentation Index

​What is Dynamic Programming?

​Pattern Recognition Checklist

Use DP When

Don't Use When

​When to Use

Optimal Substructure

Overlapping Subproblems

Counting Problems

Optimization

​The IDEAL Framework

​Pattern Variations

​1. 1D DP (Linear)

​2. 2D DP (Grid/Sequence)

​3. Knapsack Pattern

​4. LCS Pattern (Two Strings)

​5. House Robber (Cannot Take Adjacent)

​6. Coin Change

​Classic Problems

​Common Mistakes

​Debugging Checklist

​DP Pattern Categories

​Complexity Quick Reference

​Interview Problems by Company

​Interview Tips

​How to Derive a DP Recurrence — The Five-Step Recipe

​DP Templates

​Top-Down (Memoization)

​Bottom-Up Tabulation (1D)

​Bottom-Up Tabulation (2D)

​Space-Optimized 1D Rolling

​Space-Optimized 2D Rolling (one row)

​Worked LeetCode Problems

​LC 70 — Climbing Stairs (Easy, 1D linear)

​LC 198 — House Robber (Medium, 1D linear)

​LC 322 — Coin Change (Medium, unbounded knapsack)

​LC 416 — Partition Equal Subset Sum (Medium, 0/1 knapsack)

​LC 1143 — Longest Common Subsequence (Medium, 2D string)

​LC 300 — Longest Increasing Subsequence (Medium, two approaches)

​LC 72 — Edit Distance (Medium-Hard, 2D string)

​LC 5 — Longest Palindromic Substring (Medium, interval DP)

​Curated LeetCode List

​Practice Problems

​Practice Roadmap

​Interview Questions

​Interview Deep-Dive

​LeetCode Interview Q&A

What is Dynamic Programming?

Pattern Recognition Checklist

When to Use

The IDEAL Framework

Pattern Variations

1. 1D DP (Linear)

2. 2D DP (Grid/Sequence)

3. Knapsack Pattern

4. LCS Pattern (Two Strings)

5. House Robber (Cannot Take Adjacent)

6. Coin Change

Classic Problems

Common Mistakes

Debugging Checklist

DP Pattern Categories

Complexity Quick Reference

Interview Problems by Company

Interview Tips

How to Derive a DP Recurrence — The Five-Step Recipe

DP Templates

Top-Down (Memoization)

Bottom-Up Tabulation (1D)

Bottom-Up Tabulation (2D)

Space-Optimized 1D Rolling

Space-Optimized 2D Rolling (one row)

Worked LeetCode Problems

LC 70 — Climbing Stairs (Easy, 1D linear)

LC 198 — House Robber (Medium, 1D linear)

LC 322 — Coin Change (Medium, unbounded knapsack)

LC 416 — Partition Equal Subset Sum (Medium, 0/1 knapsack)

LC 1143 — Longest Common Subsequence (Medium, 2D string)

LC 300 — Longest Increasing Subsequence (Medium, two approaches)

LC 72 — Edit Distance (Medium-Hard, 2D string)

LC 5 — Longest Palindromic Substring (Medium, interval DP)

Curated LeetCode List

Practice Problems

Practice Roadmap

Interview Questions

Interview Deep-Dive

LeetCode Interview Q&A