Najdłuższy wspólny podciąg
Wyrównywanie dwóch napisów za pomocą tabeli DP
Najdłuższy wspólny podciąg to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Czym jest podciąg
Podciąg zachowuje kolejność znaków, ale może pomijać niektóre z nich. Z ciągu 'abcde' można wybrać 'ace', ale nigdy 'aec'.
Cel LCS
Dla dwóch napisów najdłuższy wspólny podciąg to najdłuższa sekwencja, która występuje w obu napisach w tej samej kolejności względnej.
Przejdź do siatki
Należy porównywać prefiksy obu napisów. Dwuwymiarowa tabela oparta na ich długościach zamienia ten problem w znany problem DP na siatce.
Zdefiniuj stan
Niech dp[i][j] oznacza długość LCS dla pierwszych i znaków A oraz pierwszych j znaków B.
Gdy znaki się zgadzają
Jeśli A[i-1] jest równe B[j-1], wspólny znak wydłuża LCS. Należy dodać jeden do wartości na przekątnej dp[i-1][j-1].
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1Gdy znaki się różnią
Jeśli znaki się różnią, należy usunąć jeden znak z dowolnego napisu i zachować lepszy wynik. Wybieramy max z dwóch sąsiadów.
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])Przypadek bazowy
Pusty prefiks nie ma żadnego wspólnego znaku z innym prefiksem, więc długość LCS wynosi zero. Wiersz 0 i kolumna 0 pozostają wypełnione samymi zerami.
dp = [[0] * (m+1) for _ in range(n+1)]Jeden dodatkowy wiersz i kolumna
Utworzenie tabeli o rozmiarze n+1 na m+1 zapewnia pustą, wyzerowaną krawędź. Eliminuje to uciążliwe sprawdzanie zakresu przy krawędziach.
Wypełnij tabelę
Należy iterować po i oraz j, zaczynając od 1. Każda komórka potrzebuje tylko wartości z góry, z lewej i z przekątnej, które zostały już obliczone.
for i in range(1, n+1):
for j in range(1, m+1):
...Odczytaj długość
Pełna długość LCS znajduje się w rogu. Odpowiedzią jest dp[n][m] po wypełnieniu wszystkich komórek.
length = dp[n][m]Złożoność
Każda komórka jest odwiedzana raz, więc czas i pamięć mają złożoność O(n times m). To z łatwością wystarcza dla napisów o długości do kilku tysięcy znaków.
Szybkie sprawdzenie
Bieżące znaki A[i-1] i B[j-1] są równe. Która aktualizacja jest poprawna?
Podsumowanie: LCS
Należy zbudować tabelę n+1 na m+1: przy zgodności dodać jeden do wartości na przekątnej, a w przeciwnym razie wybrać większego sąsiada. W rogu znajduje się długość. 🔗
Często zadawane pytania
Czy lekcja „Najdłuższy wspólny podciąg” jest bezpłatna?
Tak — pełny tekst „Najdłuższy wspólny podciąg” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Najdłuższy wspólny podciąg”?
Wyrównywanie dwóch napisów za pomocą tabeli DP Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Najdłuższy wspólny podciąg”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Zliczanie ścieżek na siatce
- Minimalna suma ścieżki z przeszkodami
- Najdłuższy wspólny podciąg
- Odległość edycyjna krok po kroku