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 — 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, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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, and the DSA Interview Prep course includes 4 lessons in total. 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.
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; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
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