Memoisation: cacha rekursiva resultat
Tillämpa @functools.lru_cache och manuella memo-dict på Fibonacci och climbing-stairs för att eliminera exponentiell omberäkning.
Memoisation: cacha rekursiva resultat är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 4 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Problemet med redundant rekursion
Naiv rekursiv Fibonacci beräknar samma värden upprepade gånger. fib(5) anropar fib(4) och fib(3); fib(4) anropar fib(3) och fib(2) – alltså beräknas fib(3) två gånger. Denna redundans växer exponentiellt: fib(40) gör över en miljard funktionsanrop. Memoisering löser detta genom att lagra varje resultat första gången det beräknas, så att efterföljande anrop hämtar det på O(1) i stället för att beräkna om det.
# Count calls without memoisation
call_count = [0]
def fib_plain(n):
call_count[0] += 1
if n <= 1: return n
return fib_plain(n-1) + fib_plain(n-2)
fib_plain(20)
print(f'fib(20) without memo: {call_count[0]:,} calls')
# ~21,891 calls for n=20; ~1 billion for n=40Manuell memoisering med en dict
Lägg till en memo-dict som parameter (eller använd en closure). Kontrollera före beräkningen om svaret redan finns i memo. Om det gör det returnerar ni det direkt. Om inte beräknar ni svaret, lagrar det i memo och returnerar det. Varje unikt delproblem beräknas nu exakt en gång, vilket omvandlar O(2^n) till O(n) tid och O(n) utrymme för memo-dict:en, plus O(n) stackutrymme.
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
print(fib_memo(10)) # 55
print(fib_memo(50)) # 12586269025
print(fib_memo(100)) # huge number — still fast!Dekoratorn functools.lru_cache
Python tillhandahåller @functools.lru_cache(maxsize=None) (även tillgänglig som @functools.cache i Python 3.9+) för att automatisera memoisering. När ni lägger till denna dekorator ovanför en funktion cachelagras alla anrop utifrån deras argument. maxsize=None innebär obegränsad cachestorlek – varje unik kombination av argument cachelagras. På så sätt omvandlas vilken rekursiv funktion som helst till en memoiserad version med en enda kodrad.
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)) # 354224848179261915075
print(fib.cache_info()) # CacheInfo(hits=..., misses=..., maxsize=None, currsize=...)Climbing Stairs (LeetCode 70)
LeetCode 70 ‘Climbing Stairs’: man kan klättra ett eller två steg åt gången. Hur många sätt finns det att nå steg n? Detta är Fibonacci i en annan form: ways(n) = ways(n-1) + ways(n-2). Basfall: ways(0) = 1 (ett sätt att stanna kvar på marknivån), ways(1) = 1. Med memoisering blir tidskomplexiteten O(n) och utrymmeskomplexiteten O(n).
import functools
@functools.lru_cache(maxsize=None)
def climbStairs(n):
if n <= 1:
return 1
return climbStairs(n-1) + climbStairs(n-2)
for i in range(1, 8):
print(f'climbStairs({i}) = {climbStairs(i)}')
# 1,2,3,5,8,13,21Coin Change (LeetCode 322)
LeetCode 322 ‘Coin Change’: givet valörer och ett målbelopp ska ni hitta det minsta antalet mynt. Top-down-rekursion med memoisering: dp(amount) = 1 + min(dp(amount - coin)) för varje giltigt mynt. Basfallet är dp(0) = 0. Cachelagra varje delbelopp. Om ett delbelopp inte kan lösas returnerar ni oändlighet. Memoisering omvandlar den exponentiella brute force-lösningen till tidskomplexiteten O(amount × len(coins)).
import functools
def coinChange(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(rem):
if rem == 0:
return 0
if rem < 0:
return float('inf')
return 1 + min(dp(rem - c) for c in coins)
result = dp(amount)
return result if result != float('inf') else -1
print(coinChange([1, 5, 11], 15)) # 3 (5+5+5)
print(coinChange([1, 2, 5], 11)) # 3 (5+5+1)
print(coinChange([2], 3)) # -1Word Break (LeetCode 139) med memo
LeetCode 139 ‘Word Break’: avgör om en sträng kan delas upp i ord från en ordlista. Top-down-rekursionen can_break(s, start) provar varje prefix s[start:end]; om prefixet finns i ordlistan och can_break(s, end) är sant returnerar ni true. Utan memoisering är detta O(2^n); med memo (där varje startindex cachelagras) blir det O(n² × L), där L är den maximala ordlängden.
import functools
def wordBreak(s, wordDict):
word_set = set(wordDict)
@functools.lru_cache(maxsize=None)
def can_break(start):
if start == len(s):
return True
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and can_break(end):
return True
return False
return can_break(0)
print(wordBreak('leetcode', ['leet', 'code'])) # True
print(wordBreak('applepenapple', ['apple','pen'])) # True
print(wordBreak('catsandog', ['cats','dog','sand','and','cat'])) # FalseMemoisering kontra tabulering
Memoisering (top-down) börjar med det ursprungliga problemet och cachelagrar svar när de upptäcks rekursivt. Den löser endast de delproblem som faktiskt behövs. Tabulering (bottom-up) fyller i en tabell från små delproblem till stora och löser alla delproblem oavsett om de behövs. Memoisering är lättare att härleda från en rekursiv lösning; tabulering undviker begränsningar i rekursionsdjupet och kostnaden för funktionsanrop.
# Memoisation (top-down)
import functools
@functools.lru_cache(maxsize=None)
def fib_td(n):
if n <= 1: return n
return fib_td(n-1) + fib_td(n-2)
# Tabulation (bottom-up)
def fib_bu(n):
if n <= 1: return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fib_td(20), fib_bu(20)) # 6765 6765
# Both O(n) time; fib_bu avoids recursion limitUtrymmesoptimering: rullande variabler
Många DP-problem som memoiserad rekursion löser med O(n) utrymme kan optimeras ytterligare till O(1) utrymme när endast ett fast antal tidigare svar på delproblem behövs. För Fibonacci är det bara de två senaste värdena som spelar roll. Detsamma gäller för climbing stairs. Två rullande variabler ersätter hela memo-dict:en eller tabellen.
# Fibonacci with O(1) space
def fib_o1(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev2 + prev1
return prev1
for i in range(8):
print(f'fib({i})={fib_o1(i)}', end=' ')
print()
# Climbing stairs O(1) space
def climbStairs_o1(n):
if n <= 1: return 1
a, b = 1, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(climbStairs_o1(10)) # 89lru_cache kontra closure kontra global dict
Det finns tre sätt att implementera memoisering manuellt. En global dict är enkel men förorenar modulens globala namnrymd. En closure kapslar in cachen i funktionen, vilket förhindrar läckage men kräver en wrapper. @lru_cache är den renaste lösningen – en enda dekorator ersätter all standardkod. I en intervju bör ni börja med @lru_cache, såvida intervjuaren inte uttryckligen ber om en manuell implementation.
import functools
# 1. Global dict (messy)
memo_global = {}
def fib_global(n):
if n in memo_global: return memo_global[n]
if n <= 1: return n
memo_global[n] = fib_global(n-1) + fib_global(n-2)
return memo_global[n]
# 2. Closure (cleaner scope)
def make_fib():
cache = {}
def fib(n):
if n in cache: return cache[n]
if n <= 1: return n
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
return fib
fib_closure = make_fib()
# 3. lru_cache (best)
@functools.lru_cache(maxsize=None)
def fib_cached(n):
if n <= 1: return n
return fib_cached(n-1) + fib_cached(n-2)
print(fib_global(30), fib_closure(30), fib_cached(30)) # all 832040När memoisering inte hjälper
Memoisering snabbar endast upp problem med överlappande delproblem – fall där samma delproblem beräknas flera gånger. Om alla delproblem är unika, som vid enkel trädtraversering där varje nod besöks exakt en gång, medför memoisering extra kostnad utan någon nytta. Memoisering kan inte heller lösa problem där det rekursiva trädet är exponentiellt i antalet distinkta delproblem, snarare än att växa exponentiellt på grund av återanvändning – sådana problem kräver en helt annan algoritm.
# Memoisation DOES help: overlapping sub-problems (Fibonacci)
# fib(n) reuses fib(n-2), fib(n-3), etc.
# Memoisation does NOT help: distinct sub-problems (permutations)
# Each unique (remaining_elements, target) pair is truly distinct
# The exponential complexity comes from the state space itself
print('Memoisation: useful when SAME sub-problem recurs multiple times')
print('Not useful: when every sub-problem is unique to one recursive path')Sammanfattning: checklista för memoisering
Tillämpa memoisering när: ni har en rekursiv lösning som är korrekt men långsam på grund av redundanta omberäkningar, funktionen har ett litet antal distinkta argumentkombinationer och returvärdet enbart beror på argumenten (en ren funktion – inga sidoeffekter och inget globalt tillstånd). Kontrollera delproblemets tillståndsrymd: om det finns högst O(n) eller O(n²) distinkta tillstånd omvandlar memoisering exponentiell tid till polynomisk tid.
Snabbkontroll
Testa er förståelse av koncepten Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionssammanfattning
I den här lektionen lärde ni er att memoisering lagrar resultat från delproblem för att undvika omberäkningar och omvandlar exponentiell rekursion till polynomisk tid, att @functools.lru_cache är det idiomatiska Python-verktyget och bara kräver en kodrad, samt att memoisering (top-down) och tabulering (bottom-up) är de två DP-stilarna – memoisering är lättare att härleda och tabulering undviker problem med stackdjupet. Grattis – ni har slutfört modulerna om rekursion och hash maps!
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Memoisation: cacha rekursiva resultat” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Memoisation: cacha rekursiva resultat”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”Memoisation: cacha rekursiva resultat”?
Tillämpa @functools.lru_cache och manuella memo-dict på Fibonacci och climbing-stairs för att eliminera exponentiell omberäkning. Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Memoisation: cacha rekursiva resultat”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Rekursionsramverk: basfall, tillit, bygg
- Visualisera anropsstacken
- Avvägningar mellan rekursiva och iterativa lösningar
- Memoisation: cacha rekursiva resultat