Top-Down DP with Memoisation
Add a memo dict to a recursive solution to prune duplicate calls, and use @lru_cache to memoize with minimal code.
Top-Down DP: The Memoisation Idea
Top-down DP starts with the original recursive solution and adds memoisation: a cache that stores the result of each sub-problem the first time it is computed. On subsequent calls with the same arguments, the cached result is returned immediately without recursion. This transforms an O(2^n) naive recursion into O(n) with minimal code changes — often just adding 2-3 lines to an existing recursive solution.
# Top-down approach:
# 1. Write the recursive solution (natural but slow)
# 2. Add a memo dict to cache results
# 3. Before recursing, check if the result is cached
# 4. Before returning, store the result in the cache
# This is also called 'memoization' (US spelling)
# 'memoize' means 'to remember', not 'memorize'
# The cache key is the function arguments
# For fib: key is n
# For 2D DP: key is (i, j)
# For 3D DP: key is (i, j, k)
print('Top-down = recursion + memo cache')Memoised Fibonacci
Adding a memo dictionary to the naive Fibonacci recursion reduces time from O(2^n) to O(n). The first call to fib(k) computes and stores the result. All subsequent calls for the same k return the cached value instantly. Space complexity is O(n) for the memo dict plus O(n) for the call stack. Compare the call counts: without memo, fib(30) makes ~2 million calls; with memo, exactly 30 calls.
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n] # return cached result
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
# Verify speed improvement:
print(fib_memo(30)) # fast!
print(fib_memo(50)) # still fast
print(fib_memo(100)) # no problem
# Without memo, fib_naive(50) would take minutes
# With memo: each of the 50 sub-problems computed onceAll lessons in this course
- Recognising DP: Overlapping Sub-Problems
- Top-Down DP with Memoisation
- Bottom-Up DP with Tabulation
- Coin Change and Min-Cost Staircase