Memoizzazione senza ricorsione
Lezione 5 di 15 del corso Programmazione dinamica 101 di Coddy.
Nella lezione precedente abbiamo imparato cos'è la memoizzazione e come può contribuire a migliorare la complessità temporale delle nostre soluzioni ricorsive. In questa lezione esploreremo come usare la ricorsione con la memoizzazione per risolvere i problemi in modo più efficiente.
La ricorsione è una tecnica di programmazione in cui una funzione richiama sé stessa per risolvere un problema. Le soluzioni ricorsive possono essere molto eleganti e intuitive, ma anche inefficienti, soprattutto se la stessa funzione viene chiamata più volte con gli stessi argomenti. È qui che entra in gioco la memoizzazione. Memorizzando i risultati delle chiamate precedenti alle funzioni, possiamo evitare calcoli ridondanti e migliorare notevolmente le prestazioni delle nostre soluzioni ricorsive.
Sfida
FacileSupponi di poter salire 1 o 2 gradini alla volta.
Scrivi una funzione chiamata count_ways che accetta un numero intero n e restituisce il numero di modi per salire una scala di n gradini.
La funzione dovrebbe essere memorizzata per evitare calcoli ripetuti.
Evita di usare la ricorsione in questa sfida!
Provalo tu
def count_ways(n):
# TODO: scrivi il tuo codice quiTutte 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