Dynamic Programming: Overlapping Subproblems and Memoization
Data Structures & AlgorithmsLesson 1 of 45 min read
What you'll learn
- Recognise overlapping subproblems and optimal substructure in a problem statement
- Count the redundant calls a naive recursion makes and explain why they happen
- Add memoization with a dictionary and with functools.lru_cache
- Know when memoization breaks: mutable arguments and Python's recursion limit
On this page
A conference organiser has a room for 400 minutes and a pool of talks that are either 20 or 30 minutes long. She wants to know how many different back-to-back running orders exist. A short recursive function answers the question for 100 minutes instantly and then appears to hang at 600. Nothing is wrong with the logic. The function is doing the same sums again and again, and dynamic programming is the discipline of noticing that and stopping it.
Write the recursion first
Every DP solution starts as a plain recursive definition. Define schedules(m) as the number of ordered ways to fill exactly m minutes. The first talk is either 20 or 30 minutes, so the answer is the ways to fill what remains after a 20-minute opener plus the ways after a 30-minute opener. Filling exactly zero minutes counts as one way (the empty schedule); a negative remainder is impossible.
calls = 0
def schedules(minutes):
"""Ordered ways to fill a room booking with 20- and 30-minute talks."""
global calls
calls += 1
if minutes == 0:
return 1
if minutes < 0:
return 0
return schedules(minutes - 20) + schedules(minutes - 30)
for total in (100, 200, 300, 400):
calls = 0
ways = schedules(total)
print(f"{total:>3} min: {ways:>4} schedules, {calls:>6} calls")Output
100 min: 7 schedules, 41 calls 200 min: 114 schedules, 701 calls 300 min: 1897 schedules, 11683 calls 400 min: 31572 schedules, 194457 calls
Look at the call counts, not the answers. Adding 100 minutes multiplies the work by roughly sixteen. That is exponential growth: each call spawns two more, and the tree of calls keeps branching. Yet there are only a few dozen distinct values of minutes the function can ever be asked about (400, 380, 370, 360 and so on down to zero). Almost all of those 194,457 calls are repeats.
The two properties that make a problem DP-shaped
- Overlapping subproblems. The same smaller question is asked many times. Here, "how many ways to fill 340 minutes" is reached via 20+20+20 as well as 30+30 and 20+30+30 in different orders, so it is recomputed from scratch each time.
- Optimal substructure. The answer to the big question is built from answers to smaller ones using a simple rule (here, a sum). If combining sub-answers is not enough to build the whole answer, DP does not apply directly.
A quick test: draw the call tree for a tiny input and look for identical nodes. If the same argument tuple shows up in two branches, you have overlap. If every node is unique, as in a simple tree traversal or plain merge sort, caching gains nothing and recursion is already optimal.
Memoization: remember what you computed
Memoization keeps the recursion exactly as written and adds a dictionary keyed by the arguments. Before computing, look the answer up; after computing, store it. The state here is just minutes, so the key is one integer.
calls = 0
memo = {}
def schedules(minutes):
global calls
calls += 1
if minutes == 0:
return 1
if minutes < 0:
return 0
if minutes in memo:
return memo[minutes]
memo[minutes] = schedules(minutes - 20) + schedules(minutes - 30)
return memo[minutes]
print(schedules(400), "schedules,", calls, "calls,", len(memo), "distinct states")Output
31572 schedules, 79 calls, 39 distinct states
The same 31,572 answer now needs 79 calls instead of 194,457. The work is bounded by the number of distinct states times the work per state. That product is how you state the complexity of any DP: 39 states with two constant-time transitions each.
The one-line version
Python ships the dictionary pattern as a decorator. functools.lru_cache(maxsize=None) wraps a function so repeated calls with equal arguments return the stored result.
from functools import lru_cache
@lru_cache(maxsize=None)
def schedules(minutes):
if minutes == 0:
return 1
if minutes < 0:
return 0
return schedules(minutes - 20) + schedules(minutes - 30)
print(schedules(2000))
print(schedules.cache_info())Output
1094081998015776526179329 CacheInfo(hits=197, misses=202, maxsize=None, currsize=202)
cache_info() is a handy way to confirm your reasoning: 202 misses means 202 distinct states were computed, and everything else was a hit. Python integers are unbounded, so the huge answer is exact.
Common mistakes and the symptoms they cause
| Mistake | What you see | Fix |
|---|---|---|
Passing a list or dict into an lru_cache function | TypeError: unhashable type: 'list' | Pass a tuple, or an index into data stored outside the function |
Recursing 5,000 levels deep (for example schedules(100000) with 20-minute steps) | RecursionError: maximum recursion depth exceeded; CPython's default limit is 1000 | Convert to a bottom-up loop (next lesson) rather than raising the limit blindly |
| Caching on too few arguments, such as leaving out a remaining-budget parameter | Plausible but wrong answers that change with call order | Write down what the answer depends on, and make all of it part of the key |
| Memoising a function that has side effects or reads global state that changes | Stale answers after the data changes | Keep memoised functions pure, or clear the cache when inputs change |
The unhashable error is easy to reproduce: decorate a function with lru_cache, call it with [1, 2] as an argument, and Python raises TypeError: unhashable type: 'list' because the cache needs a hashable key. The recursion error is similar: the schedule for 100,000 minutes needs about 5,000 nested calls, far past CPython's default limit of 1000.
How this shows up in real projects and interviews
In interviews, the usual opening is a statement like "count the ways", "find the minimum cost" or "is it possible to reach", where brute force clearly enumerates a tree. The expected path is: state the recursive definition, point out the repeated subproblems, add memoization, then state the complexity as states times transition cost. Interviewers value the second step most, because it shows you saw why the brute force is slow rather than pattern-matching to a memorised solution.
A useful way to rehearse is to take any recursive solution you have written and add a call counter, exactly as the first snippet does. If the counter grows far faster than the answer or the input size, you have found a candidate. If the counter equals the number of nodes in a tree you were traversing anyway, leave it alone. Building that instinct, rather than memorising solutions, is what lets you handle a problem you have never seen.
In real projects you rarely write textbook DP. You meet the same idea as caching of pure functions: price calculation, permission resolution, dependency analysis. The reasoning is identical: pure function, hashable inputs, bounded number of distinct inputs.
Try it yourself
A courier can move along a street of N numbered doors by skipping 1, 2 or 4 doors per hop. Write routes(n) that counts the hop sequences that land exactly on door n starting from door 0. First write it with plain recursion and count calls for n = 30, then add memoization and compare the call counts.
Show a hint
Base cases: routes(0) is 1 and routes of a negative number is 0. The answer for n is the sum of routes(n-1), routes(n-2) and routes(n-4).
Key takeaways
- DP applies when a problem has overlapping subproblems and optimal substructure; start by writing the plain recursion.
- Count calls on a small input to prove that work repeats before reaching for a cache.
- Memoization stores results by argument, so complexity becomes number of states times work per state.
lru_cacheneeds hashable arguments, and deep recursion hits Python's default limit of 1000 frames.
Test yourself
A trick from this lesson's ride: Same question asked twice? Cache it. Every question unique? Leave it alone. Four more tricks like it wait along the route, each followed by a question.
Frequently asked questions
What is the difference between memoization and dynamic programming?
Memoization is one technique for doing dynamic programming: you write the recursion top-down and cache results. Dynamic programming is the broader idea of solving a problem by combining answers to overlapping subproblems, which you can also implement bottom-up with a table, as covered in the next lesson.
How do I know if a problem needs dynamic programming?
Look for a question asking for a count, a minimum, a maximum or a yes/no over many combinations, where a brute-force recursion would re-ask the same smaller question. Draw a tiny call tree and check for repeated nodes. If none repeat, try greedy or divide and conquer instead.
Why does lru_cache raise unhashable type list?
The cache stores results in a dictionary keyed by the arguments, and lists are mutable so Python refuses to hash them. Convert the argument to a tuple, or restructure the function to take indices into data that lives outside it.