DP Foundations: The Two Pillars and Five Questions

Phase 4 | Week 24

Before you solve a single DP problem, you need these mental models locked in. Everything else in this phase is an application of what’s on this page. Read it carefully. Come back to it when you’re stuck on a problem and can’t figure out the state.

The Two Pillars of DP

DP applies when a problem has both of the following properties:

1. Overlapping Subproblems

The same smaller problem needs to be solved more than once during the computation. This is what distinguishes DP from divide-and-conquer.

  • Divide and conquer (Merge Sort, Quick Sort): Subproblems are independent. Merging two halves never reuses work from the other half. No caching needed.

  • DP (Fibonacci, Coin Change): Subproblems overlap. To compute fib(5), you compute fib(3) twice if you’re naive. Caching saves exponential repeated work.

If your recursion tree has no repeated nodes, it’s not a DP problem — it’s D&C.

2. Optimal Substructure

The optimal solution to the whole problem can be constructed from optimal solutions to subproblems. You don’t need to re-examine subproblem solutions once they’re computed — the best answer to a subproblem is always useful for the whole problem.

Example: Shortest path in a graph has optimal substructure. If the shortest path from A to C goes through B, then the A→B segment must also be the shortest path from A to B. If it weren’t, you could replace it with a shorter one and get a shorter A→C path — contradiction.

Counterexample: Longest simple path does NOT have optimal substructure, which is why it’s NP-hard while shortest path is polynomial.

Top-Down: Memoization

Start with the natural recursive solution. Add a cache. Done.

memo = {}

def solve(i, ...):
    if (i, ...) in memo:
        return memo[(i, ...)]
    
    # base case
    if i == 0:
        return base_value
    
    # recursive case
    result = some_function(solve(i-1, ...), ...)
    memo[(i, ...)] = result
    return result

When to use top-down:

  • The recursion is naturally easy to express

  • Not all subproblems need to be solved (sparse subproblem space)

  • You want to write the solution quickly and verify correctness before optimizing

Drawback: Recursive call stack overhead. In languages without tail-call optimization (Java, C++), deep recursion can stack overflow.

Bottom-Up: Tabulation

Fill a table starting from base cases, working up to the answer. No recursion.

dp = [0] * (n + 1)
dp[0] = base_value  # base case

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

return dp[n]

When to use bottom-up:

  • All subproblems must be solved anyway

  • You want to avoid stack overflow risk

  • You want to optimize space (you can discard old table entries)

Drawback: You must figure out the correct iteration order. If dp[i] depends on dp[j] where j > i, you can’t iterate left to right.

Space Optimization

When your recurrence only looks back a fixed number of steps, you don’t need to store the entire table.

Fibonacci: fib(n) = fib(n-1) + fib(n-2) only needs the last two values.

# O(n) space (full table)
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]

# O(1) space (rolling variables)
a, b = 0, 1
for _ in range(n-1):
    a, b = b, a + b
return b

2D → 1D optimization: For problems where dp[i][j] only depends on dp[i-1][j] and dp[i][j-1], you can keep only the current and previous rows — O(cols) space instead of O(rows × cols).

State Design: The Hardest Skill

State design is the answer to: “What does dp[i] (or dp[i][j]) actually mean?”

A well-defined state must:

  1. Fully capture everything you need to make a decision at that point

  2. Not include redundant information

  3. Lead to a clean transition (the recurrence relation)

The single most common DP mistake is defining the state too vaguely. If you define dp[i] as “something about the first i elements” without being precise, your transitions will be wrong.

Bad: dp[i] = “answer for the first i elements” (what does “answer” mean? best sum? count of ways? can we reach here?)

Good: dp[i] = “maximum sum of a subarray ending at index i” or “number of ways to make change for amount i using the first j coin types”

Two Examples of State Definition Errors

Error 1 — House Robber gone wrong: Suppose you define dp[i] = “maximum money robbing from houses 0..i” without tracking whether house i was robbed.

  • Your transition wants to say: if I rob house i, I must skip house i-1

  • But dp[i-1] tells you the max over houses 0..i-1, which might include house i-1

  • You can’t determine whether the last house was robbed

Fix: Either define dp[i] = “max money from 0..i where house i IS robbed” and dp2[i] = “max money where house i is NOT robbed”, or recognize that dp[i] = max(dp[i-2] + nums[i], dp[i-1]) already encodes this correctly.

Error 2 — Knapsack off by one: Students frequently define dp[w] = “max value with capacity exactly w” when they mean “max value with capacity at most w”. These have different base cases. dp[0] = 0 in both cases, but the transition dp[w] = max(dp[w], dp[w - weight[i]] + value[i]) is valid for “at most” but incorrect if interpreted as “exactly” (because dp[w - weight[i]] might be -infinity if no combination reaches exactly that weight).

The 5 Questions to Ask Every DP Problem

Apply these in order before writing a single line of code:

  1. What are the states? What information do I need at each step? What indices, counts, or flags define a unique subproblem?

  2. What are the transitions? How does the answer for state (i, j, ...) depend on smaller states? Write the recurrence explicitly.

  3. What are the base cases? What are the simplest subproblems whose answers are obvious? (Empty array, zero items, zero capacity, etc.)

  4. What is the answer? Which state holds the final answer? Is it dp[n]? dp[n][W]? max(dp[i]) over all i?

  5. Can I optimize space? Does my recurrence only look back a constant number of steps? If so, I can reduce from O(n²) table to O(n) or O(1).

Write the answers to all 5 questions before coding. If you can’t answer question 2, you don’t understand the problem yet.

What Most Engineers Get Wrong

The failure pattern is almost always the same: they skim a solution, code it up, submit, pass, and move on. Two weeks later, they can’t reproduce it. They memorized the answer, not the reasoning.

The correct workflow:

  1. Identify the pattern (1D? knapsack? 2D grid?)

  2. Define state explicitly in writing

  3. Derive the transition from first principles

  4. Identify base cases

  5. Code it

If you always do step 2 and 3 in writing before touching a keyboard, your DP accuracy will roughly triple.

Practice Before Moving On

Before proceeding to 02_1d_and_linear_dp.md, be able to answer these from memory:

  • What two properties must a problem have for DP to apply?

  • What’s the difference between memoization and tabulation?

  • What are the 5 questions to ask any DP problem?

  • Give an example of a bad state definition and explain why it breaks the transition

Navigation ← Phase 4 README | Next: 1D Linear DP →