DSA Interview Prep · Lektion

Memoization: caching af rekursive resultater

Anvend @functools.lru_cache og manuelle memo-dicts på Fibonacci og climbing-stairs for at eliminere eksponentiel genberegning.

Lektion 4 af 413 trin

Memoization: caching af rekursive resultater er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.

Problemet med overflødig rekursion

Naiv rekursiv Fibonacci beregner de samme værdier igen og igen. fib(5) kalder fib(4) og fib(3); fib(4) kalder fib(3) og fib(2) — så fib(3) beregnes to gange. Denne overflødighed vokser eksponentielt: fib(40) udfører over en milliard funktionskald. Memoisering løser dette ved at gemme hvert resultat første gang, det beregnes, så efterfølgende kald henter det på O(1) i stedet for at beregne det igen.

# 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=40

Manuel memoisering med en Dict

Tilføj en memo-ordbog som parameter (eller brug en lukning). Før beregningen skal du kontrollere, om svaret allerede findes i memo. Hvis ja, returnér det straks. Hvis nej, beregn det, gem det i memo, og returnér det. Hvert unikt delproblem beregnes nu præcis én gang, så O(2^n) bliver til O(n)-tid og O(n)-plads til memo-ordbogen plus O(n) stakplads.

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!

functools.lru_cache-dekorator

Python har @functools.lru_cache(maxsize=None) (også tilgængelig som @functools.cache i Python 3.9+) til automatisk memoisering. Når du tilføjer denne dekorator over en funktion, caches alle kald baseret på deres argumenter. maxsize=None betyder ubegrænset cachestørrelse — enhver unik argumentkombination caches. Det konverterer enhver rekursiv funktion til en memoiseret version med én kodelinje.

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=...)

Klatring på trapper (LeetCode 70)

LeetCode 70 'Klatring på trapper': Du kan gå 1 eller 2 trin ad gangen. Hvor mange måder er der til at nå trin n? Dette er Fibonacci i forklædning: ways(n) = ways(n-1) + ways(n-2). Basistilfælde: ways(0) = 1 (én måde at blive på jorden), ways(1) = 1. Med memoisering er tidsforbruget O(n), og pladsforbruget er 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,21

Møntskift (LeetCode 322)

LeetCode 322 'Møntskift': Givet møntværdier og et målbeløb skal du finde det mindste antal mønter. Memoiseret rekursion oppefra og ned: dp(amount) = 1 + min(dp(amount - coin)) for hver gyldig mønt. Basistilfældet er: dp(0) = 0. Gem hvert delbeløb i cachen. Hvis et delbeløb er umuligt, returnér uendelig. Memoisering omdanner den eksponentielle udtømmende søgning til O(amount × len(coins))-tid.

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))          # -1

Orddeling (LeetCode 139) med memoisering

LeetCode 139 'Orddeling': Afgør, om en streng kan opdeles i ordbogsord. Rekursion oppefra og ned: can_break(s, start) prøver hvert præfiks s[start:end]; hvis det findes i ordbogen, og can_break(s, end) er sand, returnér sand. Uden memo er det O(2^n); med memo (hvor hvert startindeks caches) bliver det O(n² × L), hvor L er den maksimale ordlængde.

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']))  # False

Memoisering vs. tabulering

Memoisering (oppefra og ned) starter med det oprindelige problem og gemmer svar, efterhånden som de opdages rekursivt. Den løser kun de delproblemer, der faktisk er nødvendige. Tabulering (nedefra og op) udfylder på forhånd en tabel fra små delproblemer til store og løser alle delproblemer uanset behov. Memoisering er lettere at udlede fra en rekursiv løsning; tabulering undgår begrænsninger på rekursionsdybden og overhead ved funktionskald.

# 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 limit

Pladsoptimering: Rullende variabler

Mange DP-problemer, som memoiseret rekursion løser med O(n)-plads, kan optimeres yderligere til O(1)-plads, når der kun er brug for et fast antal tidligere svar på delproblemer. For Fibonacci er det kun de to seneste værdier, der betyder noget. Det samme gælder for klatring på trapper. To rullende variabler erstatter hele memo-ordbogen 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))  # 89

lru_cache vs. lukning vs. global Dict

Der er tre måder at implementere memoisering manuelt på. En global ordbog er enkel, men forurener modulets omfang. En lukning indkapsler cachen i funktionen, hvilket forhindrer lækage, men kræver en indpakningsfunktion. @lru_cache er den reneste løsning — én dekorator erstatter al standardkoden. I et interview bør du starte med @lru_cache, medmindre intervieweren specifikt beder om en manuel implementering.

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 832040

Hvornår memoisering ikke hjælper

Memoisering fremskynder kun problemer med overlappende delproblemer — tilfælde, hvor det samme delproblem beregnes flere gange. Hvis hvert delproblem er unikt (som ved et simpelt træ-gennemløb, hvor hver knude besøges præcis én gang), tilføjer memoisering overhead uden fordel. Memoisering kan heller ikke løse problemer, hvor rekursionstræet er eksponentielt i antallet af forskellige delproblemer snarere end på grund af genbrug af delproblemer — de kræver en helt anden algoritme.

# 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')

Opsummering: Tjekliste til memoisering

Anvend memoisering, når: du har en rekursiv løsning, der er korrekt, men langsom på grund af overflødige genberegninger, funktionen har et lille antal forskellige argumentkombinationer, og returværdien kun afhænger af argumenterne (ren funktion — ingen bivirkninger, ingen global tilstand). Undersøg delproblemets tilstandsrum: Hvis der højst er O(n) eller O(n²) forskellige tilstande, omdanner memoisering eksponentiel tid til polynomiel tid.

Hurtig kontrol

Test din forståelse af begreberne fra Data Structures & Algorithms — Coding Interview Prep i denne lektion.

Besvar den i den interaktive lektion

Opsummering af lektionen

I denne lektion lærte du: memoisering gemmer resultater af delproblemer for at undgå genberegning og omdanner eksponentiel rekursion til polynomiel tid, @functools.lru_cache er det idiomatiske Python-værktøj, der kun kræver én linje, og memoisering (oppefra og ned) og tabulering (nedefra og op) er de to DP-stilarter — memoisering er lettere at udlede, mens tabulering undgår problemer med stakdybden. Tillykke — du har gennemført modulerne om rekursion og hashtabeller!

Gratis at komme i gang

Lær Python med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 30
Lektioner: 120

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Memoization: caching af rekursive resultater” gratis?

Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Memoization: caching af rekursive resultater”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Memoization: caching af rekursive resultater”?

Anvend @functools.lru_cache og manuelle memo-dicts på Fibonacci og climbing-stairs for at eliminere eksponentiel genberegning. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på DSA Interview Prep?

Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.

Hvor lang tid tager lektionen “Memoization: caching af rekursive resultater”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?

Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

Rekursionsramme: basistilfælde, tillid, opbygning
Visualisering af kaldestakken
Afvejninger mellem rekursiv og iterativ kode
Memoization: caching af rekursive resultater

← Tilbage til DSA Interview Prep