Najdłuższy wspólny podciąg
Lekcja 6 z 15 w kursie Programowanie dynamiczne — podstawy w Coddy.
Najdłuższy wspólny podciąg (LCS) to klasyczny problem informatyczny polegający na znalezieniu najdłuższego podciągu wspólnego dla dwóch ciągów. Podciąg to ciąg, który można uzyskać z innego ciągu przez usunięcie niektórych lub żadnych elementów bez zmiany kolejności pozostałych elementów.
Na przykład rozważmy dwa ciągi:
S1 = "AGGTAB"
S2 = "GXTXAYB"
LCS ciągów S1 i S2 to "GTAB" o długości 4.
Istnieje kilka sposobów rozwiązania problemu LCS, a najpopularniejszym z nich jest programowanie dynamiczne.
Wyzwanie
ŚredniNapisz funkcję, która przyjmuje dwa ciągi znaków jako dane wejściowe i zwraca długość ich najdłuższego wspólnego podciągu.
Uwaga: ten algorytm (podobnie jak nadchodzące algorytmy w tym kursie) jest uznawany za zaawansowany i nowym programistom może być trudno samodzielnie wymyślić wydajne rozwiązanie z użyciem programowania dynamicznego. Nie wahaj się korzystać z podpowiedzi lub przycisku 'Ask AI'!
Spróbuj swoich sił
def longest_common_subsequence(str1, str2):
# Napisz kod tutajWszystkie lekcje w sekcji Programowanie dynamiczne — podstawy
1Wprowadzenie do programowania dynamicznego
Czym jest programowanie dynamiczne?Dlaczego jest ważne?Zastosowania w różnych dziedzinach4Zaawansowane zagadnienia
Minimalna długość podtablicyPrzycinanieOptymalizacja pamięciMaskowanie bitów3Algorytmy programowania dynamicznego
Najdłuższy wspólny podciągProblem plecakowyProblem wydawania resztyOdległość edycyjnaPoćwicz samodzielnie: Kompilator Python online