Riepilogo dei concetti chiave
Lezione 14 di 15 del corso Programmazione dinamica 101 di Coddy.
In questa lezione, ripasseremo i concetti chiave trattati nel corso Dynamic Programming 101.
- Programmazione dinamica: la programmazione dinamica è una tecnica per risolvere problemi di ottimizzazione scomponendoli in sottoproblemi più semplici e risolvendo ogni sottoproblema una sola volta.
- Memoizzazione: la memoizzazione è una tecnica per evitare calcoli ridondanti memorizzando i risultati delle chiamate a funzione costose e restituendo il risultato memorizzato nella cache quando si ripresentano gli stessi input.
- Tabulazione: la tabulazione è una tecnica per risolvere problemi di programmazione dinamica compilando iterativamente una tabella o un array di soluzioni, fino a raggiungere la soluzione finale.
- Sottostruttura ottimale: un problema presenta una sottostruttura ottimale se la sua soluzione ottimale contiene al suo interno soluzioni ottimali dei suoi sottoproblemi.
- Sottoproblemi sovrapposti: un problema presenta sottoproblemi sovrapposti se può essere scomposto in sottoproblemi che condividono sotto-sottoproblemi.
- Ottimizzazione dello spazio: l'ottimizzazione dello spazio è una tecnica per ridurre i requisiti di memoria di un algoritmo di programmazione dinamica tenendo traccia solo dello stato necessario.
- Mascheramento di bit: il mascheramento di bit è una tecnica che usa la manipolazione dei bit per rappresentare un insieme di elementi come un numero binario.
- Potatura: la potatura è una tecnica usata per ridurre il numero di calcoli richiesti da un algoritmo di programmazione dinamica evitando calcoli non necessari.
Sfida
MedioSfida di ripasso: percorso a costo minimo
Ti viene data una griglia n x n che rappresenta una mappa della città. Ogni cella della griglia rappresenta un incrocio stradale e i valori nelle celle rappresentano il costo per attraversare quell'incrocio. Vuoi viaggiare dall'angolo in alto a sinistra della griglia a quello in basso a destra e puoi muoverti solo verso il basso o verso destra a ogni incrocio.
Scrivi una funzione min_cost_path(grid) che riceve la griglia come input e restituisce il costo minimo per attraversarla dall'angolo in alto a sinistra a quello in basso a destra.
Per esempio:
grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
min_cost_path(grid) => 7Spiegazione: il percorso a costo minimo è 1 -> 3 -> 1 -> 1 -> 1, con un costo totale di 7.
Provalo tu
def min_cost_path(grid):
# Scrivi il 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