Pattern 13 of 18 · Dynamic Programming

1-D Dynamic Programming

Break a problem into overlapping subproblems along a single dimension.

Break a problem into overlapping subproblems along a single dimension — like "the answer up to index i" — solve each one once, and reuse the result instead of recomputing it.

Key concepts

  • Optimal substructure: the answer for the whole problem can be built from answers to smaller versions of itself.
  • Overlapping subproblems: naive recursion would solve the same subproblem many times — DP solves it once and remembers it.
  • Memoization (top-down): recursion plus a cache. Tabulation (bottom-up): an iterative array built from the base case upward.
  • State: usually `dp[i]` — the answer considering only the first `i` elements.

When to use it

  • A greedy or purely recursive approach recomputes the same subproblem repeatedly.
  • The problem asks for a count, a minimum/maximum, or a yes/no reachability over a sequence, where the answer at position `i` depends on answers at earlier positions.

Tips

  • Start by writing the brute-force recursive solution — the DP recurrence is often just that same recursion, cached.
  • Define what `dp[i]` means in one sentence before writing any code — most bugs come from a fuzzy state definition.
  • Once the recurrence works, check whether you actually need the whole array or just the last one or two values — that's an easy space optimization.

Practice problems (12)

Blind 75 (10):

More from Blind 150 (2):

← Advanced Graphs2-D Dynamic Programming →

See the full roadmap →