Dynamic programming is recursion without redundancy. That single sentence captures the entire idea. You take a problem that has a natural recursive structure, notice that the recursion recomputes the same subproblems over and over, and then eliminate that waste by storing results you have already computed. The speedup is often dramatic - from exponential to polynomial.

The best way to understand this is through the Fibonacci sequence. The definition is recursive: fib(n) = fib(n-1) + fib(n-2), with base cases fib(0) = 0 and fib(1) = 1. Here is the naive recursive implementation:

This looks clean, but it is catastrophically slow. To compute fib(5), the function calls fib(4) and fib(3). Then fib(4) calls fib(3) and fib(2). Notice that fib(3) is computed twice - once by fib(5) and once by fib(4). As n grows, this redundancy explodes. The recursion tree branches at every node, producing roughly 2^n total calls. Computing fib(50) with this code would take over a million billion operations.

The recursion tree for fib(6) makes the waste visible. The subtree for fib(3) appears three times. The subtree for fib(2) appears five times. Every one of those repeated subtrees does the exact same computation and returns the exact same result. Dynamic programming says: compute each subproblem once, store the result, and look it up when you need it again.

With that single change - storing results - the time complexity drops from O(2^n) to O(n). You compute fib(0), fib(1), fib(2), ..., fib(n) exactly once each. That is n+1 computations instead of 2^n. For n = 50, that is 51 operations instead of over a quadrillion.

Why the Name

Richard Bellman coined the term in the 1950s. The word 'programming' refers to planning and optimization (as in 'linear programming'), not computer programming. 'Dynamic' was chosen partly because it sounded impressive. The name is confusing, but the technique is straightforward: solve each subproblem once, store the answer, reuse it.

When DP Applies

Dynamic programming works when a problem has two properties:

1. Overlapping subproblems - the recursive solution solves the same subproblem multiple times
2. Optimal substructure - the optimal solution to the problem includes optimal solutions to its subproblems

If only one property holds, DP is not the right tool. Binary search has optimal substructure (the answer is in one half) but no overlapping subproblems (each half is visited at most once). A problem with overlapping subproblems but no optimal substructure (like finding the longest simple path in a graph) cannot be solved with DP either.

The next section breaks down these two properties in detail.