Dynamic Programming — Introduction
Learn what dynamic programming is, why it exists, and how to recognize when a problem can be solved with it.
Dynamic Programming
Dynamic programming (DP) is a technique for solving problems by breaking them into overlapping subproblems and storing the results of each subproblem so they are never computed more than once. It turns exponential-time solutions into polynomial-time ones.
The name is misleading — it has nothing to do with "dynamic" in the programming sense. The word was chosen for bureaucratic reasons in the 1950s. Think of it instead as smart recursion with a memory.
The core idea — overlapping subproblems
Consider naive recursive Fibonacci:
def fibonacci(n):
if n <= 1: return n
return fibonacci(n - 1) + fibonacci(n - 2)This works but is catastrophically slow. fibonacci(5) calls fibonacci(3) twice — once directly, once through fibonacci(4). fibonacci(3) calls fibonacci(1) three times. The same subproblems are solved over and over.
The two properties that make DP applicable
1. Overlapping subproblems — the same smaller problems appear multiple times. Pure divide and conquer (merge sort, binary search) does NOT have this — each subproblem is unique.
2. Optimal substructure — the optimal solution to the problem can be built from optimal solutions to its subproblems. The shortest path from A to C through B is the shortest path from A to B plus the shortest path from B to C.
If a problem has both properties, dynamic programming applies.
Two approaches to DP
Memoization (top-down) — write the natural recursion, add a cache. When a subproblem is solved, store the result. When it appears again, return the cached value.
Tabulation (bottom-up) — solve the smallest subproblems first, store them in a table, and build up to the final answer. No recursion needed.
Both give the same asymptotic complexity. Memoization is often easier to write. Tabulation avoids recursion stack overhead and is usually faster in practice.
When to use DP
These are the signals that a problem might be solvable with DP:
| Signal | Example |
|---|---|
| "maximum" or "minimum" value | Minimum coins to make change |
| "number of ways" | Number of paths through a grid |
| "can it be done" | Can we partition the array into equal sums |
| Decision at each step | At each house, rob or skip |
| Future depends on past choices | Longest increasing subsequence |
The hardest part of dynamic programming is not writing the code — it is figuring out the recurrence relation: how the answer to a problem of size n relates to answers to smaller problems. Once you have the recurrence, the code is usually straightforward.
The three steps to solve a DP problem
Step 1 — define the state. What information do you need to describe a subproblem? For Fibonacci, the state is just n. For longest common subsequence, the state is (i, j) — positions in both strings.
Step 2 — write the recurrence. How does dp[n] relate to dp[n-1], dp[n-2], etc.? This is the heart of the solution.
Step 3 — identify the base cases. What are the smallest subproblems you can answer directly? fibonacci(0) = 0, fibonacci(1) = 1.
What is coming in this section
Memoization — top-down DP with caching, including @lru_cache and manual dictionaries.
Tabulation — bottom-up DP filling a table, and space optimization techniques.
Classic problems — Fibonacci, coin change, 0/1 knapsack, longest common subsequence, and longest increasing subsequence.