Scrolls
4 min read
On this page

Dynamic Programming

Dynamic programming is the most feared interview topic, and the least understood. Engineers treat it as a category of exotic problems that require flashes of insight. It is not. DP is recursion with caching. If you can write a recursive solution, you can write a DP solution. The only new idea is: do not recompute the same thing twice.

What DP Actually Is

Every DP solution follows the same three steps:

1. Define the subproblem: What smaller question do I need to answer?
2. Write the recurrence: How does the answer to a bigger problem
   relate to answers to smaller problems?
3. Add memoization (or build a table): Cache results so each
   subproblem is solved exactly once.

That is it. Everything else — top-down vs bottom-up, state compression, optimization tricks — is refinement of these three steps.

Recognizing DP Problems

Two properties indicate a problem can be solved with DP:

Overlapping subproblems: The same subproblem is solved multiple times. This is what makes caching worthwhile. If every subproblem is unique, you just have plain recursion.

Optimal substructure: The optimal solution to the full problem can be built from optimal solutions to its subproblems.

Problem clues that suggest DP:
  - "Find the minimum/maximum..."
  - "Count the number of ways..."
  - "Is it possible to..."
  - "Find the longest/shortest..."
  - Decision-making at each step (take or skip, include or exclude)
  - Problem has clear stages or positions

Top-Down (Memoization)

Start with the recursive solution, then add a cache. This is the most natural approach and the one you should default to in interviews.

Problem: Fibonacci numbers
  fib(0) = 0, fib(1) = 1
  fib(n) = fib(n-1) + fib(n-2)

Naive recursion (exponential — O(2^n)):
  def fib(n):
      if n <= 1:
          return n
      return fib(n-1) + fib(n-2)

With memoization (O(n)):
  memo = {}
  def fib(n):
      if n in memo:
          return memo[n]
      if n <= 1:
          return n
      memo[n] = fib(n-1) + fib(n-2)
      return memo[n]

The recursive call tree for fib(5) without memoization recomputes fib(3) twice, fib(2) three times, and fib(1) five times. Memoization ensures each value is computed exactly once.

Bottom-Up (Tabulation)

Instead of starting from the top and recursing down, start from the smallest subproblems and build up.

Fibonacci bottom-up:
  dp = [0] * (n + 1)
  dp[0] = 0
  dp[1] = 1

  for i in range(2, n + 1):
      dp[i] = dp[i-1] + dp[i-2]

  return dp[n]

Space-optimized (only need the last 2 values):
  prev2, prev1 = 0, 1
  for i in range(2, n + 1):
      curr = prev1 + prev2
      prev2 = prev1
      prev1 = curr
  return prev1

Top-Down vs Bottom-Up

Top-down (memoization):
  + More natural — start with the recursive solution you already have
  + Only computes subproblems that are actually needed
  + Easier to reason about correctness
  - Recursion stack can overflow for large inputs
  - Function call overhead

Bottom-up (tabulation):
  + No recursion stack overhead
  + Can be space-optimized more easily
  + Slightly faster in practice (no function call overhead)
  - Must figure out the correct iteration order
  - Computes all subproblems, even unused ones

In interviews, default to top-down. It is faster to write and easier to explain. Switch to bottom-up if the interviewer asks for optimization or if the recursion depth is a concern.

Classic DP Patterns

The Knapsack Pattern

You have items with weights and values. You have a capacity. Maximize the total value without exceeding the capacity.

0/1 Knapsack: Each item can be taken or left.

  Subproblem: dp[i][w] = max value using items 0..i with capacity w

  Recurrence:
    dp[i][w] = max(
        dp[i-1][w],                      # skip item i
        dp[i-1][w - weight[i]] + value[i] # take item i (if it fits)
    )

  Base case: dp[0][w] = 0 for all w (no items)
             dp[i][0] = 0 for all i (no capacity)

  Time: O(n * W). Space: O(n * W), optimizable to O(W).

The knapsack pattern applies to many problems beyond literal knapsacks:

- Subset sum: Can you select elements summing to target? (values = weights)
- Partition equal subset: Can you split array into two equal-sum subsets?
- Target sum with +/-: Assign + or - to each number to reach target.

Longest Common Subsequence (LCS)

Problem: Find the length of the longest subsequence common to two strings.
  "abcde" and "ace" -> LCS is "ace", length 3

  Subproblem: dp[i][j] = LCS of first i chars of s1 and first j chars of s2

  Recurrence:
    if s1[i-1] == s2[j-1]:
        dp[i][j] = dp[i-1][j-1] + 1       # chars match, extend LCS
    else:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # skip one or the other

  Base case: dp[0][j] = 0, dp[i][0] = 0

  Time: O(m * n). Space: O(m * n), optimizable to O(min(m, n)).

LCS variants include: longest common substring (consecutive match), edit distance (add insert/delete/replace costs), and diff algorithms.

Coin Change

Problem: Find the fewest coins to make a target amount.
  coins = [1, 5, 10, 25], target = 30

  Subproblem: dp[amount] = fewest coins to make this amount

  Recurrence:
    dp[amount] = min(dp[amount - coin] + 1) for each coin <= amount

  Base case: dp[0] = 0 (zero coins for zero amount)
  Initialize: dp[1..target] = infinity (not yet achievable)

  for amount in range(1, target + 1):
      for coin in coins:
          if coin <= amount and dp[amount - coin] != infinity:
              dp[amount] = min(dp[amount], dp[amount - coin] + 1)

  return dp[target] if dp[target] != infinity else -1

  Time: O(amount * num_coins). Space: O(amount).

The "number of ways" variant uses addition instead of min:

  dp[amount] += dp[amount - coin]

Grid Paths

Problem: Count the number of paths from top-left to bottom-right
of an m x n grid, moving only right or down.

  Subproblem: dp[i][j] = number of paths to cell (i, j)

  Recurrence:
    dp[i][j] = dp[i-1][j] + dp[i][j-1]   # from above + from left

  Base case: dp[0][j] = 1, dp[i][0] = 1   # only one way along edges

  Time: O(m * n). Space: O(m * n), optimizable to O(n).

Grid path variants include: obstacles (set dp = 0 for blocked cells), minimum cost path (use min instead of addition and add cell costs), and maximum path sum.

The DP Problem-Solving Process

When you encounter a DP problem in an interview, follow this process:

Step 1: Identify the decision at each step.
  "Do I take this item or skip it?"
  "Do I come from the left, above, or diagonal?"
  "Which coin do I use next?"

Step 2: Define the state.
  What information do I need to make the decision?
  This becomes the parameters of your recursive function
  or the dimensions of your DP table.

Step 3: Write the recurrence.
  Express dp[current_state] in terms of dp[smaller_states].

Step 4: Identify the base cases.
  What are the smallest subproblems with known answers?

Step 5: Implement top-down with memoization.
  Write the recursive solution with a cache.

Step 6: Optimize if asked.
  Convert to bottom-up. Reduce space if only recent states
  are needed.

Walk through this process out loud in the interview. Even if you do not reach a perfect solution, showing the structured approach gives strong signal.

State Definition Strategies

The hardest part of DP is defining the right state. Some guidelines:

Common state variables:
  - Index/position (which element are we considering?)
  - Remaining capacity/budget
  - Previous choice (when the current decision depends on the last)
  - Boolean flags (have we used a special ability? is a condition met?)

If your recurrence does not work, your state is probably wrong.
Common fixes:
  - Add a dimension (e.g., add "number of transactions so far")
  - Change what the state represents
  - Redefine the subproblem entirely

Worked Example: House Robber

Problem: Rob houses along a street. Cannot rob two adjacent houses.
Maximize total value.
  houses = [2, 7, 9, 3, 1]

Step 1: Decision at house i: rob it or skip it.

Step 2: State: dp[i] = max money robbing from houses 0..i.

Step 3: Recurrence:
  dp[i] = max(
      dp[i-1],              # skip house i
      dp[i-2] + houses[i]   # rob house i (can't rob i-1)
  )

Step 4: Base cases: dp[0] = houses[0], dp[1] = max(houses[0], houses[1])

Step 5: Implementation:
  dp = [0] * len(houses)
  dp[0] = houses[0]
  dp[1] = max(houses[0], houses[1])

  for i in range(2, len(houses)):
      dp[i] = max(dp[i-1], dp[i-2] + houses[i])

  return dp[-1]

Trace:
  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 -> 2 + 9 + 1 = 12)

Common Pitfalls

  • Jumping to DP without trying recursion first: Always start with a brute-force recursive solution. Then add memoization. Trying to build a bottom-up table from scratch is error-prone for complex problems.
  • Wrong state definition: If your recurrence does not produce correct results, the most likely problem is that your state does not capture enough information. Add dimensions before trying to fix the recurrence.
  • Forgetting base cases: Every recursive path must eventually reach a base case. Missing base cases cause infinite recursion or wrong results.
  • Off-by-one in table dimensions: If your state is dp[i] for items 0..n-1, the table needs n entries. If your state is dp[i][j] for a grid of size m x n, the table is m x n. Double-check dimensions.
  • Not recognizing DP problems: If a greedy approach gives wrong results but the problem has optimal substructure, it is probably DP. Try a small counterexample for the greedy approach to confirm.
  • Premature optimization: Do not try to space-optimize or convert to bottom-up during your first pass. Get a correct top-down solution first. Optimize only when asked or when the solution works correctly.
  • Treating DP as a category of tricks: DP is a technique (cache recursive results), not a collection of problems to memorize. Understanding the technique lets you solve novel problems; memorizing solutions does not.

Key Takeaways

  • DP is recursion with caching. If you can write the recursive solution, adding memoization gives you DP. That is the entire concept.
  • Start with top-down memoization in interviews. It is faster to write, easier to explain, and naturally correct. Convert to bottom-up only if asked.
  • Recognizing DP problems comes from the two properties: overlapping subproblems and optimal substructure. Practice identifying these before jumping to solutions.
  • The four classic patterns (knapsack, LCS, coin change, grid paths) cover the vast majority of interview DP problems. Understand the recurrence for each, not just the code.
  • Walk through the problem-solving process out loud: identify decisions, define state, write recurrence, establish base cases, implement. This structured approach gives strong interview signal even if you do not reach the optimal solution.