Potatura
Lezione 11 di 15 del corso Programmazione dinamica 101 di Coddy.
Il pruning è una tecnica usata per ridurre il numero di calcoli richiesti da un algoritmo di programmazione dinamica, evitando calcoli non necessari. Questo si ottiene eliminando alcuni rami dell’albero ricorsivo che non porteranno a una soluzione migliore della migliore soluzione trovata finora. Il pruning può essere usato sia negli algoritmi di programmazione dinamica top-down sia in quelli bottom-up.
Sfida
EspertoIn questa sfida, ti viene fornita una matrice di numeri interi e un valore obiettivo. Il tuo compito è scegliere un numero intero da ogni riga della matrice, in modo che la differenza assoluta tra il valore obiettivo e la somma dei numeri interi scelti sia minima. Dovrai quindi restituire il valore di questa differenza assoluta minima.
Provalo tu
def minimize_difference(mat, target):
# 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