Ottimizzazione dello spazio
Lezione 12 di 15 del corso Programmazione dinamica 101 di Coddy.
Nella programmazione dinamica, spesso usiamo una tabella o una matrice per memorizzare le soluzioni dei sottoproblemi. Tuttavia, in alcuni casi, la tabella può essere troppo grande e consumare troppa memoria. È qui che entra in gioco l’ottimizzazione dello spazio. Le tecniche di ottimizzazione dello spazio vengono usate per ridurre la memoria necessaria a risolvere un problema di programmazione dinamica.
Una popolare tecnica di ottimizzazione dello spazio consiste nell’usare array circolari, noti anche come array scorrevoli. Invece di memorizzare l’intera tabella, se ne memorizza solo una parte alla volta e i valori precedenti vengono scartati man mano che vengono calcolati nuovi valori. Questo può ridurre significativamente la memoria necessaria a risolvere un problema.
Sfida
DifficileIn questa sfida, ti viene fornito un array di numeri interi. Il tuo compito è trovare la lunghezza della sottosequenza crescente più lunga (LIS) nell'array. Una sottosequenza crescente è una sequenza di numeri nell'array in cui ogni numero è maggiore del precedente. La LIS è la più lunga di queste sottosequenze. Devi implementare la soluzione usando tecniche di ottimizzazione dello spazio.
Provalo tu
def lis_length(arr):
# Scrivi il codice quiTutte le lezioni di Programmazione dinamica 101
1Introduzione alla DP
Che cos’è la programmazione dinamica?Perché è importante?Applicazioni in vari campi4Argomenti avanzati
lunghezza_minima_sottoarrayPotaturaOttimizzazione dello spazioMascheramento dei bit3Algoritmi di programmazione dinamica
Sottosequenza comune più lungaProblema dello zainoProblema del cambio delle moneteDistanza di modificaEsercitati da solo: Compilatore Python online