Memoisering mot tabulering
To måter å mellomlagre svar på delproblemer
Memoisering mot tabulering er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hvorfor mellomlagre i det hele tatt
Naiv rekursjon gjør det samme arbeidet om og om igjen. Dynamisk programmering lagrer hvert svar én gang, slik at du aldri trenger å beregne det på nytt.
fib(40) # slow: recomputes endlesslyOverlappende delproblemer
DP passer når et problem kan deles opp i overlappende delproblemer. Det samme mindre tilfellet dukker opp i mange grener av rekursjonen.
fib(5) needs fib(3) twiceTop-down: Memoisering
Memoisering er vanlig rekursjon med en hurtigbuffer. Du beregner ved behov og husker resultatet første gang du ser hvert input.
memo = {}Enkel memo i Python
Dekoratoren lru_cache gjør langsom rekursjon om til rask DP med én linje, ved å mellomlagre hvert kall automatisk.
from functools import lru_cache
@lru_cache(None)
def f(n): ...Bottom-up: Tabulering
Tabulering fyller ut en tabell fra de minste tilfellene og opp til svaret, ved å bruke en løkke i stedet for rekursjon.
dp = [0] * (n + 1)En tabulert Fibonacci
Sett grunnverdiene, og la deretter hver celle lese verdiene som allerede er beregnet. Ingen kallstakk, bare en ryddig 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, ulik stil
Memoisering og tabulering løser den samme rekurrensen. De skiller seg bare i retning: top-down ved behov eller bottom-up i rekkefølge.
Når du bør foretrekke memoisering
Velg memoisering når rekurrensen er naturlig å skrive, og du kanskje ikke trenger alle tilstandene.
Når du bør foretrekke tabulering
Velg tabulering for effektive løkker, for å unngå feil på grunn av rekursjonsgrensen, og når du uansett skal beregne hele tabellen.
import sys; sys.setrecursionlimit(10**6)Følg med på rekursjonsgrensen
Dyp rekursjon med memoisering kan nå Pythons rekursjonsgrense og krasje med en kjøretidsfeil på store inndata.
Begge deler har én felles kostnad
Uansett kommer hastighetsøkningen fra å løse hver tilstand én gang. Den totale tiden er antallet tilstander multiplisert med arbeidet per tilstand.
Hurtigsjekk
Hvilken metode fyller ut en tabell bottom-up med en løkke?
Oppsummering: To veier, én DP
Du kan mellomlagre delproblemer på to måter. Memoisering bruker rekursjon top-down, mens tabulering bruker løkker bottom-up. Velg den løsningen som er enklest å lese. ✨
Lær deg Forberedelse til kodeintervjuer 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
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Memoisering mot tabulering» gratis?
Ja – hele teksten i «Memoisering mot tabulering» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Memoisering mot tabulering»?
To måter å mellomlagre svar på delproblemer Du øver på Forberedelse til kodeintervjuer 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 Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer 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 1 av 4.
Hvor lang tid tar leksjonen «Memoisering mot tabulering»?
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 Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-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
- Memoisering mot tabulering
- Definer tilstand og overgang
- Trappegang og myntkombinasjoner
- Lengste økende delsekvens