Memoization versus tabulation
Twee manieren om antwoorden op deelproblemen te cachen
Memoization versus tabulation is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Competitive Programming Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Waarom überhaupt cachen
Naïeve recursie doet steeds opnieuw hetzelfde werk. Dynamische programmering slaat elk antwoord één keer op, zodat je het nooit opnieuw berekent.
fib(40) # slow: recomputes endlesslyOverlappende deelproblemen
DP is geschikt wanneer een probleem uiteenvalt in overlappende deelproblemen. Dezelfde kleinere situatie komt in veel vertakkingen van de recursie terug.
fib(5) needs fib(3) twiceVan boven naar beneden: memoization
Memoization is gewone recursie met een cache. Je berekent waarden wanneer dat nodig is en onthoudt het resultaat wanneer je elke invoer voor het eerst ziet.
memo = {}Eenvoudige memoization in Python
De decorateur lru_cache maakt trage recursie met één regel tot snelle DP en cachet automatisch elke aanroep.
from functools import lru_cache
@lru_cache(None)
def f(n): ...Van onder naar boven: tabulation
Tabulation vult een tabel vanaf de kleinste gevallen tot aan het antwoord, met een lus in plaats van recursie.
dp = [0] * (n + 1)Fibonacci met tabulation
Stel de basiswaarden in en laat daarna elke cel de waarden lezen die al berekend zijn. Geen aanroepstack, alleen een overzichtelijke lus.
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Hetzelfde antwoord, een andere stijl
Memoization en tabulation lossen dezelfde recurrentie op. Alleen de richting verschilt: van boven naar beneden wanneer nodig, of van onder naar boven in volgorde.
Wanneer je memoization verkiest
Kies memoization wanneer de recurrentie natuurlijk te schrijven is en je mogelijk niet elke toestand nodig hebt.
Wanneer je tabulation verkiest
Kies tabulation voor efficiënte lussen, om fouten door de recursielimiet te vermijden en wanneer je toch de hele tabel berekent.
import sys; sys.setrecursionlimit(10**6)Let op de recursielimiet
Diepe recursie met memoization kan de Python-recursielimiet bereiken en bij grote invoer crashen met een runtimefout als resultaat.
Beide hebben dezelfde kosten
In beide gevallen komt de versnelling doordat je elke toestand één keer oplost. De totale tijd is het aantal toestanden maal het werk per toestand.
Snelle controle
Welke aanpak vult met een lus een tabel van onder naar boven?
Samenvatting: twee routes, één DP
Je kunt deelproblemen op twee manieren cachen. Memoization gebruikt recursie van boven naar beneden; tabulation gebruikt lussen van onder naar boven. Kies de aanpak die het duidelijkst leest. ✨
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Memoization versus tabulation” gratis?
Ja — de volledige tekst van “Memoization versus tabulation” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Competitive Programming Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat leer ik in “Memoization versus tabulation”?
Twee manieren om antwoorden op deelproblemen te cachen Je oefent met Competitive Programming Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Competitive Programming Academy te beginnen?
Ervaring vooraf is niet nodig. Competitive Programming Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “Memoization versus tabulation”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Competitive Programming Academy?
Ja. Elke les over Competitive Programming Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Memoization versus tabulation
- Toestand en transitie definiëren
- Trappen beklimmen en muntcombinaties
- Langste stijgende subsequence