Dynamic Programming: Introduction to Overlapping Subproblems & Optimal Substructure

Dynamic programming (DP) is a technique for solving a problem by breaking it into smaller subproblems, solving each subproblem once, and reusing the stored answer instead of recomputing it. It applies whenever a problem has two properties — overlapping subproblems and optimal substructure — and it turns many exponential brute-force recursions into fast polynomial solutions. This page explains those two properties and how to recognize when DP is the right tool.

The core idea: don’t repeat work

Consider computing the n-th Fibonacci number with plain recursion: fib(n) = fib(n-1) + fib(n-2). The recursion tree recomputes fib(3), fib(2), and so on an exponential number of times. DP says: the moment you compute an answer for a subproblem, remember it. The next time you need it, look it up in O(1).

// Naive: exponential O(2^n) — recomputes the same values endlessly
long long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

// Naive: exponential O(2^n) — recomputes the same values endlessly
long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

// Naive: exponential O(2^n) — recomputes the same values endlessly
function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

# Naive: exponential O(2^n) — recomputes the same values endlessly
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Property 1: Overlapping subproblems

A problem has overlapping subproblems when the same smaller problems are solved many times. Fibonacci is the textbook case: fib(5) needs fib(3) twice, fib(2) three times, and so on. Because the subproblems repeat, caching their results pays off enormously.

For beginners: Contrast this with merge sort. Merge sort also splits into subproblems, but each half is distinct — they never overlap — so caching gains nothing. That is plain divide and conquer, not DP.

Property 2: Optimal substructure

A problem has optimal substructure when an optimal solution to the whole can be built from optimal solutions to its parts. The shortest path from A to C through B is the shortest A→B path plus the shortest B→C path. If this composition holds, you can define the answer with a recurrence: a formula expressing the answer in terms of smaller answers.

The three ingredients of every DP

To design a DP, always pin down three things:

1. State — what a subproblem is, captured by the minimal set of parameters (e.g. dp[i] = answer for the first i items).
2. Transition (recurrence) — how to compute a state from smaller states.
3. Base cases — the smallest states whose answers are known directly.

Get those three right and the code almost writes itself.

The two ways to implement DP

• Top-down (memoization): write the natural recursion, but cache each result. See memoization vs tabulation.
• Bottom-up (tabulation): fill a table from the base cases upward, no recursion.

Both compute the same states; they differ only in order and overhead.

When does DP apply?

Reach for DP when you see:

• “Count the number of ways…” or “find the minimum/maximum…” over choices.
• A brute-force recursion that branches and revisits the same arguments.
• Decisions made step by step where each step depends on previous results.

If subproblems never repeat, DP gives no speedup. If there’s a greedy choice that’s provably optimal, greedy may be simpler. DP is the safety net when greedy fails but the problem still has optimal substructure.

Complexity intuition

A DP’s time is roughly (number of states) × (work per transition). Fibonacci has n states and O(1) work each → O(n). A grid DP with m × n states and O(1) transitions → O(mn). This back-of-the-envelope estimate is your first sanity check.

Going deeper: Counting distinct states is the single most useful DP skill. If you can describe a subproblem with k small integer parameters, you have a k-dimensional table and you can usually bound the runtime immediately.

Next, learn the two implementation styles side by side in memoization vs tabulation, then meet the gateway problem in Fibonacci & Climbing Stairs.