Sottosequenza comune più lunga
Lezione 6 di 15 del corso Programmazione dinamica 101 di Coddy.
La sottosequenza comune più lunga (LCS) è un classico problema dell'informatica che consiste nel trovare la sottosequenza più lunga comune a due sequenze. Una sottosequenza è una sequenza che può essere ricavata da un'altra sequenza eliminando alcuni o nessuno dei suoi elementi, senza modificare l'ordine degli elementi rimanenti.
Per esempio, considera due sequenze:
S1 = "AGGTAB"
S2 = "GXTXAYB"
La LCS di S1 e S2 è "GTAB" e ha una lunghezza di 4.
Esistono diversi approcci per risolvere il problema della LCS; il più diffuso è quello della programmazione dinamica.
Sfida
MedioScrivi una funzione che accetti due stringhe come input e restituisca la lunghezza della loro sottosequenza comune più lunga.
Nota: questo (insieme ai prossimi algoritmi di questo corso) è considerato un algoritmo avanzato e potrebbe essere difficile per chi è alle prime armi con la programmazione trovare autonomamente una soluzione DP efficiente. Non esitare a usare i suggerimenti o il pulsante 'Ask AI'!
Provalo tu
def longest_common_subsequence(str1, str2):
# 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