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 with Memoisation is a free DSA Interview Prep lesson on CoddyKit. This is lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, and your progress syncs across the web and the CoddyKit app. The DSA Interview Prep course includes 4 lessons in total.
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 onceUsing @functools.lru_cache
Python's @functools.lru_cache(maxsize=None) decorator (or the alias @cache in Python 3.9+) automatically memoises a function based on its arguments. This is the cleanest way to add top-down DP in interview settings — write the recursive solution, slap on the decorator, done. The decorator caches all results in a dictionary keyed by the function's arguments, which must be hashable (no lists — use tuples instead).
import functools
@functools.lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
print(fib(50)) # 12586269025
print(fib(100)) # works instantly
# Clear cache between tests if needed:
fib.cache_clear()
# Python 3.9+ shorthand:
# from functools import cache
# @cache
# def fib(n): ...
print(fib.cache_info()) # shows hits, misses, maxsize, currsizeTop-Down Coin Change
Coin Change (LeetCode #322): given coin denominations and a target amount, find the minimum number of coins needed. The recursive formulation: for each coin, take it and solve for the remaining amount, then take the minimum. Memoise on the amount to avoid recomputation. Base case: amount=0 needs 0 coins; an impossible amount returns infinity (or -1 after the recursion).
import functools
def coin_change_top_down(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(remaining):
if remaining == 0:
return 0 # no coins needed
if remaining < 0:
return float('inf') # impossible
# Try each coin and take the minimum
return 1 + min(dp(remaining - c) for c in coins)
result = dp(amount)
return result if result != float('inf') else -1
print(coin_change_top_down([1, 5, 6, 9], 11)) # 2: (5+6) or (2*5+1?no: 9+2?no) 5+6=11 YES
print(coin_change_top_down([2], 3)) # -1: impossible
print(coin_change_top_down([1, 2, 5], 11)) # 3: 5+5+1Top-Down Climbing Stairs with K Steps
Generalise climbing stairs to allow 1 to k steps. The state is the current stair, and from stair i you can reach stairs i+1, i+2, ..., i+k. The recurrence: dp(i) = sum of dp(i-j) for j in 1..k if i-j >= 0. Memoisation makes this O(n*k) instead of O(k^n). This generalisation appears in problems like 'minimum cost to reach the last step' and 'count ways to fill a grid'.
import functools
def climb_k_steps(n, k):
@functools.lru_cache(maxsize=None)
def dp(i):
if i == 0:
return 1 # base: one way to stay at ground
if i < 0:
return 0 # impossible
# From stair i, you could have come from i-1, i-2, ..., i-k
return sum(dp(i - j) for j in range(1, k+1) if i - j >= 0)
return dp(n)
# k=2 (original): should match fib-like sequence
print([climb_k_steps(n, 2) for n in range(7)]) # [1,1,2,3,5,8,13]
# k=3: more options
print([climb_k_steps(n, 3) for n in range(7)]) # [1,1,2,4,7,13,24]Top-Down LCS: 2D Memoisation
The Longest Common Subsequence (LCS) requires a 2D state: dp(i, j) = LCS length of s1[:i] and s2[:j]. If s1[i-1] == s2[j-1], the characters match: dp(i,j) = 1 + dp(i-1, j-1). Otherwise: dp(i,j) = max(dp(i-1,j), dp(i,j-1)) — skip one character from either string. Memoising on (i, j) gives O(mn) instead of O(2^(m+n)).
import functools
def lcs_top_down(s1, s2):
m, n = len(s1), len(s2)
@functools.lru_cache(maxsize=None)
def dp(i, j):
if i == 0 or j == 0:
return 0 # empty prefix has LCS of 0
if s1[i-1] == s2[j-1]:
return 1 + dp(i-1, j-1) # characters match
return max(dp(i-1, j), dp(i, j-1)) # skip one
return dp(m, n)
print(lcs_top_down('abcde', 'ace')) # 3: 'ace'
print(lcs_top_down('abc', 'abc')) # 3: 'abc'
print(lcs_top_down('abc', 'def')) # 0: no common charsMemo Dict vs lru_cache: When to Choose
Use @lru_cache when your function arguments are hashable primitive types (int, str, tuple). Use a manual memo dict when: you need to pass mutable state (lists, dicts) by converting them to tuples, you need to track which keys were computed, or you are in a class method where self should not be cached. The manual memo dict is more explicit and avoids subtle closure issues in recursive helper functions.
# @lru_cache: clean, automatic, O(1) overhead
# Use when: arguments are simple (int, str, tuple)
import functools
@functools.lru_cache(maxsize=None)
def simple_dp(n):
if n <= 1: return n
return simple_dp(n-1) + simple_dp(n-2)
# Manual memo dict: explicit, flexible
# Use when: complex state, need to inspect memo, class methods
def manual_memo_dp(s1, s2):
memo = {}
def dp(i, j):
if (i,j) in memo: return memo[(i,j)]
if i == 0 or j == 0:
return 0
if s1[i-1] == s2[j-1]:
memo[(i,j)] = 1 + dp(i-1, j-1)
else:
memo[(i,j)] = max(dp(i-1,j), dp(i,j-1))
return memo[(i,j)]
return dp(len(s1), len(s2))
print(manual_memo_dp('abcde', 'ace')) # 3Top-Down Target Sum
Target Sum (LeetCode #494): assign + or - to each number and count assignments that produce a target sum. State: dp(index, current_sum). At each index, try adding (+) and subtracting (-) the current number. Memoisation on (index, current_sum) converts the O(2^n) brute force to O(n * sum_range). The sum range is bounded by the total sum of all numbers, giving O(n * S) total states.
import functools
def find_target_sum_ways(nums, target):
@functools.lru_cache(maxsize=None)
def dp(index, current_sum):
if index == len(nums):
return 1 if current_sum == target else 0
# Try adding the number
add = dp(index + 1, current_sum + nums[index])
# Try subtracting the number
subtract = dp(index + 1, current_sum - nums[index])
return add + subtract
return dp(0, 0)
print(find_target_sum_ways([1,1,1,1,1], 3)) # 5
print(find_target_sum_ways([1], 1)) # 1
print(find_target_sum_ways([1], -1)) # 1Top-Down vs Bottom-Up: Pros and Cons
Top-down (memoisation) advantages: natural to write (starts from the recursive solution), only computes sub-problems actually needed (lazy), easy to add cache incrementally. Bottom-up (tabulation) advantages: no call-stack overhead (no Python recursion limit), more cache-friendly memory access, easier to space-optimise. Both have the same asymptotic complexity. In interviews, start top-down to verify correctness, then convert to bottom-up if asked for better space.
# Top-down advantages:
# + Natural: write recursive, add @cache
# + Lazy: only computes needed sub-problems
# + Easy to reason about correctness
# - Uses call stack (recursion limit in Python)
# - Higher constant factor (function call overhead)
# Bottom-up advantages:
# + No recursion limit
# + Better cache performance (sequential memory)
# + Easier to space-optimise (rolling array)
# - Must compute all sub-problems in order
# - Less intuitive for complex 2D/3D problems
# Interview strategy:
# Start with top-down to verify recurrence,
# convert to bottom-up only if asked.
print('Top-down: easy to write | Bottom-up: efficient for large n')Word Break with Top-Down DP
Word Break (LeetCode #139) asks if a string s can be segmented into words from a dictionary. State: dp(i) = whether s[i:] can be segmented. From index i, try all words: if s[i:i+len(w)] == w, recurse on the remaining suffix. Memoisation on the starting index converts the O(2^n) brute force to O(n^2) (or O(n * max_word_len)) with the set membership check.
import functools
def word_break(s, word_dict):
word_set = set(word_dict)
@functools.lru_cache(maxsize=None)
def dp(start):
if start == len(s):
return True # successfully segmented entire string
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and dp(end):
return True
return False
return dp(0)
print(word_break('leetcode', ['leet', 'code'])) # True
print(word_break('applepenapple', ['apple', 'pen'])) # True
print(word_break('catsandog', ['cats', 'dog', 'and', 'cat', 'san', 'andog'])) # FalseRecursion Limit and Itertools
Python's default recursion limit is 1000 (set by sys.getrecursionlimit()). For DP problems on large inputs (n = 10,000+), top-down memoisation will hit this limit. Options: increase the limit with sys.setrecursionlimit(100000), or convert to bottom-up DP. In competitive programming, increasing the limit is common; in production code, always prefer bottom-up or iterative solutions for reliability.
import sys
print('Default recursion limit:', sys.getrecursionlimit()) # 1000
# For large DP problems, increase if needed:
# sys.setrecursionlimit(100000)
# Better: convert to bottom-up DP for large n
def fib_bottom_up(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n+1):
a, b = b, a + b
return b
# No recursion limit issue:
print(fib_bottom_up(10000)) # works fine, no recursionQuick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: top-down DP with a memo dict and @lru_cache decorator, memoised solutions for Fibonacci, coin change, LCS, target sum, and word break, and when to choose top-down versus bottom-up. Next up we implement bottom-up DP with tabulation and space optimisation.
Frequently Asked Questions
Is the “Top-Down DP with Memoisation” lesson free?
Yes — the full text of “Top-Down DP with Memoisation” is free to read here on the web. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO. The DSA Interview Prep course includes 4 lessons in total.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners, so you can start here or from the beginning and move at your own pace. This is lesson 2 of 4.
How long does the “Top-Down DP with Memoisation” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All 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