Memoization e tabulation a confronto
Due modi per memorizzare le risposte ai sottoproblemi
Memoization e tabulation a confronto è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Perché usare la cache
La ricorsione ingenua ripete lo stesso lavoro più e più volte. La programmazione dinamica memorizza ogni risposta una sola volta, evitando di ricalcolarla.
fib(40) # slow: recomputes endlesslySottoproblemi sovrapposti
La DP si applica quando un problema si divide in sottoproblemi sovrapposti. Lo stesso caso più piccolo ricompare in molti rami della ricorsione.
fib(5) needs fib(3) twiceDall'alto verso il basso: memoizzazione
La memoizzazione è una semplice ricorsione con una cache. Calcola i risultati quando servono e ricorda il risultato la prima volta che incontra ogni input.
memo = {}Memoizzazione semplice in Python
Il decoratore lru_cache trasforma la ricorsione lenta in DP veloce con una sola riga, memorizzando automaticamente ogni chiamata.
from functools import lru_cache
@lru_cache(None)
def f(n): ...Dal basso verso l'alto: tabulazione
La tabulazione riempie una tabella partendo dai casi più piccoli fino ad arrivare alla risposta, usando un ciclo invece della ricorsione.
dp = [0] * (n + 1)Un Fibonacci tabulato
Imposti i valori di base, quindi faccia leggere a ogni cella quelli già calcolati. Nessuno stack delle chiamate, solo un ciclo ordinato.
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Stessa risposta, stile diverso
Memoizzazione e tabulazione risolvono la stessa ricorrenza. Differiscono solo nella direzione: dall'alto verso il basso quando serve, oppure dal basso verso l'alto seguendo l'ordine.
Quando preferire la memoizzazione
Scelga la memoizzazione quando la ricorrenza è naturale da scrivere e potrebbe non essere necessario calcolare ogni stato.
Quando preferire la tabulazione
Scelga la tabulazione per cicli stretti, per evitare gli errori dovuti al limite di ricorsione e quando dovrà comunque calcolare l'intera tabella.
import sys; sys.setrecursionlimit(10**6)Attenzione al limite di ricorsione
Una ricorsione con memoizzazione molto profonda può raggiungere il limite di ricorsione di Python e terminare con un errore di esecuzione sugli input grandi.
Entrambe condividono lo stesso costo
In entrambi i casi, l'aumento di velocità deriva dal risolvere ogni stato una sola volta. Il tempo totale è dato dal numero di stati moltiplicato per il lavoro richiesto da ogni stato.
Verifica rapida
Quale approccio riempie una tabella dal basso verso l'alto usando un ciclo?
Riepilogo: due strade, una DP
Ora può memorizzare i sottoproblemi in due modi. La memoizzazione procede ricorsivamente dall'alto verso il basso; la tabulazione usa cicli dal basso verso l'alto. Scelga l'approccio più chiaro da leggere. ✨
Domande Frequenti
La lezione «Memoization e tabulation a confronto» è gratuita?
Sì — il testo completo di «Memoization e tabulation a confronto» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Memoization e tabulation a confronto»?
Due modi per memorizzare le risposte ai sottoproblemi Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Memoization e tabulation a confronto»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Memoization e tabulation a confronto
- Definire stato e transizione
- Salita delle scale e combinazioni di monete
- Sottosequenza crescente più lunga