Memoizzazione
Lezione 4 di 15 del corso Programmazione dinamica 101 di Coddy.
La memoizzazione è una tecnica di ottimizzazione usata nella programmazione dinamica per accelerare i programmi memorizzando nella cache i risultati delle chiamate a funzioni costose e restituendo il risultato memorizzato nella cache quando si ripresentano gli stessi input.
Per implementare la memoizzazione, puoi creare un dizionario in cui memorizzare i risultati già calcolati, usando gli argomenti di input come chiavi e i risultati di output corrispondenti come valori. Prima di calcolare il risultato di una funzione, puoi prima verificare se l'input è già stato calcolato e memorizzato nel dizionario. In tal caso, puoi restituire il risultato memorizzato nella cache invece di calcolarlo di nuovo. Altrimenti, calcoli il risultato e lo memorizzi nel dizionario.
listpuò essere usato anche per implementare la memoizzazione.
La memoizzazione può accelerare significativamente gli algoritmi di programmazione dinamica, soprattutto quando ci sono molti sottoproblemi sovrapposti.
Sfida
FacileScrivi una funzione Python chiamata fib che calcoli l'ennesimo numero di Fibonacci usando la memoizzazione.
- Usa il dizionario
memoper memorizzare i numeri di Fibonacci già calcolati. - Prima di calcolare l'ennesimo numero di Fibonacci, controlla se è già stato calcolato e memorizzato in
memo. - Se è così, restituisci il risultato memorizzato nella cache. Altrimenti, calcola l'ennesimo numero di Fibonacci usando la relazione di ricorrenza
fib(n) = fib(n-1) + fib(n-2)e memorizza il risultato nel dizionario per usarlo in futuro.
Suggerimento: controlla la soluzione alla fine per vedere se hai usato correttamente la memoizzazione!
Provalo tu
memo = {0: 0, 1: 1}
def fib(n):
Tutte le lezioni di Programmazione dinamica 101
1Introduzione alla DP
Che cos’è la programmazione dinamica?Perché è importante?Applicazioni in vari campi3Algoritmi di programmazione dinamica
Sottosequenza comune più lungaProblema dello zainoProblema del cambio delle moneteDistanza di modificaEsercitati da solo: Compilatore Python online