Memoization mod tabulation
To måder at cache svar på delproblemer
Memoization mod tabulation er en gratis Competitive Programming Academy-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Competitive Programming Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Competitive Programming Academy-kurset indeholder 4 lektioner i alt.
Hvorfor overhovedet bruge cache
Naiv rekursion udfører det samme arbejde igen og igen. Dynamisk programmering gemmer hvert svar én gang, så du aldrig beregner det igen.
fib(40) # slow: recomputes endlesslyOverlappende delproblemer
DP er relevant, når et problem opdeles i overlappende delproblemer. Den samme mindre sag dukker op i mange grene af rekursionen.
fib(5) needs fib(3) twiceTop-down: memoisering
Memoisering er almindelig rekursion kombineret med en cache. Du beregner efter behov og husker resultatet, første gang du ser hvert inddata.
memo = {}Nem memo i Python
Dekoratoren lru_cache forvandler langsom rekursion til hurtig DP på én linje og cacher automatisk hvert kald.
from functools import lru_cache
@lru_cache(None)
def f(n): ...Bottom-up: tabulering
Tabulering udfylder en tabel fra de mindste tilfælde op til svaret ved hjælp af en løkke i stedet for rekursion.
dp = [0] * (n + 1)En tabuleret Fibonacci
Sæt basisværdierne, og lad derefter hver celle læse dem, der allerede er beregnet. Ingen kaldestak, bare en enkel løkke.
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Samme svar, forskellig stil
Memoisering og tabulering løser den samme rekurrens. De adskiller sig kun i retningen: top-down efter behov eller bottom-up i rækkefølge.
Hvornår du bør foretrække memoisering
Vælg memoisering, når rekurrensen er naturlig at skrive, og du måske ikke får brug for alle tilstande.
Hvornår du bør foretrække tabulering
Vælg tabulering til stramme løkker, for at undgå fejl på grund af rekursionsgrænsen, og når du alligevel vil beregne hele tabellen.
import sys; sys.setrecursionlimit(10**6)Hold øje med rekursionsgrænsen
Dyb memoiseret rekursion kan ramme Pythons rekursionsgrænse og gå ned med en kørselsfejl ved bedømmelsen på store inddata.
Begge deler én omkostning
Uanset metode kommer hastighedsforbedringen af, at du løser hver tilstand én gang. Den samlede tid er antallet af tilstande gange arbejdet pr. tilstand.
Hurtig kontrol
Hvilken metode udfylder en tabel bottom-up med en løkke?
Opsummering: To veje, én DP
Du kan nu cache delproblemer på to måder. Memoisering bruger rekursion top-down, mens tabulering bruger løkker bottom-up. Vælg den, der er lettest at læse. ✨
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
Ofte stillede spørgsmål
Er lektionen “Memoization mod tabulation” gratis?
Ja — hele teksten til “Memoization mod tabulation” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Competitive Programming Academy-kurset, skal du opgradere til CoddyKit PRO. Competitive Programming Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Memoization mod tabulation”?
To måder at cache svar på delproblemer Du øver dig i Competitive Programming Academy 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å Competitive Programming Academy?
Der kræves ingen tidligere erfaring. Competitive Programming Academy 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 1 af 4.
Hvor lang tid tager lektionen “Memoization mod tabulation”?
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 Competitive Programming Academy-lektion?
Ja. Alle Competitive Programming Academy-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
- Memoization mod tabulation
- Definér tilstand og overgang
- Trappeklatring og møntkombinationer
- Længste stigende delsekvens