Top-down-DP med memoisation
Legg til en memo-dict i en rekursiv løsning for å kutte bort dupliserte kall, og bruk @lru_cache til å lagre resultater med minimalt med kode.
Top-down-DP med memoisation er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 2 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Top-down-DP: Ideen med memoisering
Top-down-DP starter med den opprinnelige rekursive løsningen og legger til memoisering: en cache som lagrer resultatet av hvert delproblem første gang det beregnes. Ved senere kall med de samme argumentene returneres det mellomlagrede resultatet umiddelbart, uten ny rekursjon. Dette gjør en naiv rekursjon på O(2^n) om til O(n) med minimale kodeendringer – ofte ved å legge til bare 2–3 linjer i en eksisterende rekursiv løsning.
# 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')Memoisert Fibonacci
Ved å legge til en memo-ordbok i den naive Fibonacci-rekursjonen reduseres tiden fra O(2^n) til O(n). Det første kallet til fib(k) beregner og lagrer resultatet. Alle påfølgende kall for samme k returnerer den mellomlagrede verdien umiddelbart. Plasskompleksiteten er O(n) for memo-ordboken pluss O(n) for kallstakken. Sammenlign antallet kall: uten memo gjør fib(30) omtrent 2 millioner kall, mens det med memo gjøres nøyaktig 30 kall.
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 onceBruk av @functools.lru_cache
Python-dekoratoren @functools.lru_cache(maxsize=None) (eller aliaset @cache i Python 3.9+) memoiserer automatisk en funksjon basert på argumentene. Dette er den ryddigste måten å legge til top-down-DP på i intervjuer – skriv den rekursive løsningen, legg på dekoratoren, og du er ferdig. Dekoratoren mellomlagrer alle resultater i en ordbok med nøkler basert på funksjonens argumenter, som må være hashbare (ingen lister – bruk tupler i stedet).
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 for Coin Change
Coin Change (LeetCode #322): Gitt myntvalører og et målbeløp skal du finne det minste antallet mynter som trengs. Den rekursive formuleringen er: For hver mynt tar du den og løser problemet for det gjenværende beløpet, og velger deretter minimumet. Memoiser på beløpet for å unngå å beregne det samme flere ganger. Basistilfellet er at amount=0 trenger 0 mynter; et umulig beløp returnerer infinity (eller -1 etter rekursjonen).
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 for Climbing Stairs med K trinn
Generaliser Climbing Stairs slik at du kan ta 1 til k trinn. Tilstanden er det gjeldende trinnet, og fra trinn i kan du nå trinn i+1, i+2, ..., i+k. Rekurrensen er: dp(i) = sum of dp(i-j) for j in 1..k if i-j >= 0. Memoisering gjør dette til O(n*k) i stedet for O(k^n). Denne generaliseringen dukker opp i problemer som «minimum cost to reach the last step» og «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-memoisering
Longest Common Subsequence (LCS) krever en 2D-tilstand: dp(i, j) = LCS-lengden til s1[:i] og s2[:j]. Hvis s1[i-1] == s2[j-1], samsvarer tegnene: dp(i,j) = 1 + dp(i-1, j-1). Ellers: dp(i,j) = max(dp(i-1,j), dp(i,j-1)) – hopp over ett tegn fra en av strengene. Memoisering basert på (i, j) gir O(mn) i stedet for 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-ordbok vs. lru_cache: Når bør du velge hva
Bruk @lru_cache når funksjonsargumentene er hashbare primitive typer (int, str, tuple). Bruk en manuell memo-ordbok når du må sende inn muterbar tilstand (lister, ordbøker) ved å konvertere den til tupler, når du må holde oversikt over hvilke nøkler som er beregnet, eller når du arbeider i en klassemetode der self ikke bør caches. Den manuelle memo-ordboken er mer eksplisitt og unngår subtile problemer med avslutninger i rekursive hjelpefunksjoner.
# @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 for Target Sum
Target Sum (LeetCode #494): Tilordne + eller - til hvert tall, og tell hvor mange tilordninger som gir en målsum. Tilstanden er: dp(index, current_sum). Ved hver indeks prøver du både å legge til (+) og trekke fra (-) det gjeldende tallet. Memoisering på (index, current_sum) gjør brute force med O(2^n) om til O(n * sum_range). Sumområdet er begrenset av totalsummen av alle tallene, noe som gir totalt O(n * S) tilstander.
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 kontra bottom-up: Fordeler og ulemper
Fordeler med top-down (memoisering): naturlig å skrive (du starter med den rekursive løsningen), beregner bare delproblemene som faktisk trengs (lazy) og gjør det enkelt å legge til cache trinnvis. Fordeler med bottom-up (tabulering): ingen overhead fra kallstakken (ingen Python-grense for rekursjon), mer cache-vennlig minnetilgang og enklere plassoptimalisering. Begge har samme asymptotiske kompleksitet. I intervjuer bør du starte med top-down for å kontrollere at løsningen er korrekt, og deretter konvertere til bottom-up hvis du blir bedt om bedre plassbruk.
# 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 med top-down-DP
Word Break (LeetCode #139) spør om en streng s kan deles opp i ord fra en ordbok. Tilstanden er: dp(i) = om s[i:] kan deles opp. Fra indeks i prøver du alle ord: hvis s[i:i+len(w)] == w, rekurrerer du på det gjenværende suffikset. Memoisering på startindeksen gjør brute force med O(2^n) om til O(n^2) (eller O(n * max_word_len)) med mengdeoppslag.
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'])) # FalseRekursjonsgrense og Itertools
Python har en standardgrense for rekursjon på 1000, satt av sys.getrecursionlimit(). For DP-problemer med store input (n = 10,000+) vil top-down-memoisering nå denne grensen. Alternativene er å øke grensen med sys.setrecursionlimit(100000) eller konvertere til bottom-up-DP. I konkurranseprogrammering er det vanlig å øke grensen; i produksjonskode bør du alltid foretrekke bottom-up- eller iterative løsninger for å oppnå pålitelighet.
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 recursionKort sjekk
Test forståelsen din av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte du om: top-down-DP med en memo-ordbok og @lru_cache-dekoratoren, memoiserte løsninger for Fibonacci, Coin Change, LCS, Target Sum og Word Break, og når du bør velge top-down fremfor bottom-up. Neste del handler om å implementere bottom-up-DP med tabulering og plassoptimalisering.
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Top-down-DP med memoisation» gratis?
Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «Top-down-DP med memoisation», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Hva lærer jeg i «Top-down-DP med memoisation»?
Legg til en memo-dict i en rekursiv løsning for å kutte bort dupliserte kall, og bruk @lru_cache til å lagre resultater med minimalt med kode. Du øver på DSA Interview Prep med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med DSA Interview Prep?
Ingen tidligere erfaring er nødvendig. DSA Interview Prep på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «Top-down-DP med memoisation»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne DSA Interview Prep-leksjonen?
Ja. Alle DSA Interview Prep-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Gjenkjenne DP: overlappende delproblemer
- Top-down-DP med memoisation
- Bottom-up-DP med tabulering
- Coin Change og trapp med minimale kostnader