What Is Dynamic Programming?

The Idea

Dynamic programming applies when two things are true: the same subproblem keeps reappearing, and the best whole answer is built from best sub-answers. Merge sort splits into fresh halves that never overlap, so caching buys nothing. Fibonacci's branches collide constantly, so caching buys everything. You already did this by hand in Memoization — DP is that habit, made deliberate.

Real-World Example

A bakery costing out its cake menu. Half the recipes share the same buttercream, so the pastry chef prices one batch of it once and pins the figure to the wall. Every cake using it reads that number instead of re-costing butter, sugar, and labour from scratch.

The Code

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):                       # the same n is asked for again and again
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(50))                    # 12586269025 — instant, because nothing repeats
print(fib.cache_info().hits)      # reads that skipped a whole subtree

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n):
  return n if n < 2 else f(n - 1) + f(n - 2)

f(10)
print(f.cache_info().misses)