DP intuition

Dynamic programming is not a data structure or a specific algorithm — it is a design strategy. Apply it when naive recursion solves the same sub-problems repeatedly and throws away results it will need again.

Two conditions for DP

A problem is a DP candidate when both of the following hold:

1. Optimal substructure. The optimal solution to the full problem contains optimal solutions to its sub-problems. Fibonacci is the simplest example: fib(n) = fib(n-1) + fib(n-2) — the correct answer for n is built entirely from correct answers to smaller inputs. Shortest path in a graph also has this property: any sub-path of a shortest path is itself a shortest path.

2. Overlapping subproblems. The recursion solves the same sub-problems more than once. This is what separates DP from divide-and-conquer: merge sort splits into disjoint halves that never share work; Fibonacci splits into halves that heavily overlap.

Why naive Fibonacci is O(2^n)

Trace fib(5):

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) → 1
│   │   │   └── fib(0) → 0
│   │   └── fib(1) → 1
│   └── fib(2)          ← computed again
│       ├── fib(1) → 1
│       └── fib(0) → 0
└── fib(3)              ← computed again
    ├── fib(2)          ← computed again
    │   ├── fib(1) → 1
    │   └── fib(0) → 0
    └── fib(1) → 1

fib(3) is computed twice, fib(2) three times, fib(1) five times. The call tree roughly doubles at each level. Formally, the number of calls grows as O(2^n) — computing fib(50) would require around 2^50 ≈ 10^15 calls.

The redundancy is not inherent to the problem — it is an artefact of throwing away results. Every call to fib(2) produces the same answer (1), but without storing it the algorithm recomputes it from scratch every time.

What DP does differently

DP stores results the first time a sub-problem is solved, then looks them up in O(1) when the same sub-problem appears again. The call tree collapses: each unique input is processed exactly once. For Fibonacci, there are only n+1 unique inputs (0 through n), so the total work drops from O(2^n) to O(n).

This storage can be done in two ways:

• Top-down (memoisation): write the recursive function, add a cache that stores results as they are computed. On the next call with the same argument, return the cached result immediately.
• Bottom-up (tabulation): fill an array from the smallest sub-problem to the largest, using only previously computed values. No recursion at all.

Both produce the same asymptotic complexity. The practical differences are explored in the next two lessons.

Recognising DP candidates

Ask these questions about an unfamiliar problem:

1. Can I define the answer in terms of answers to smaller versions of the same problem? (Optimal substructure.)
2. Would a recursive solution re-solve those smaller problems multiple times? (Overlapping subproblems.)
3. Is the answer to a given sub-problem fully determined by its inputs — no side effects, no external state? (This makes caching correct.)

If all three are yes, DP is likely the right tool. Common domains: counting ways to reach a goal, minimum-cost paths, sequence alignment, packing problems, and any "can we partition/segment this string/array?" question.

Where to go next

Next: memoisation — adding a cache to a recursive Fibonacci implementation, using @lru_cache, and watching call counts drop from exponential to linear in the browser.