Odległość edycyjna krok po kroku
Wstawianie, usuwanie i zastępowanie w celu przekształcenia
Odległość edycyjna krok po kroku to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 4 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.
Co mierzy odległość edycyjna
Odległość edycyjna to najmniejsza liczba jednoznakowych operacji edycyjnych potrzebnych do przekształcenia jednego napisu w drugi. Określa, jak bardzo dwa słowa faktycznie się różnią.
Trzy operacje
W jednej operacji można wstawić, usunąć lub zastąpić jeden znak. W standardowym problemie każda z tych operacji kosztuje dokładnie jeden.
Zdefiniuj stan
Niech dp[i][j] oznacza liczbę operacji potrzebnych do przekształcenia pierwszych i znaków A w pierwsze j znaków B.
Darmowa zgodność
Jeśli bieżące znaki już się zgadzają, nie jest potrzebna żadna operacja. Wystarczy przepisać wartość z przekątnej.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]W przeciwnym razie zapłać jeden
Gdy znaki się różnią, należy wybrać najmniejszą wartość spośród sąsiadów i dodać jedną operację. Schemat min plus jeden obejmuje wszystkie trzy operacje.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Który sąsiad oznacza którą operację
Komórka powyżej oznacza usunięcie, komórka po lewej — wstawienie, a komórka po przekątnej — zastąpienie. Funkcja min wybiera po prostu najtańszą możliwość.
Przypadki bazowe dla pustego napisu
Przekształcenie napisu o długości i w pusty napis wymaga i operacji usunięcia. Dlatego pierwszy wiersz i kolumnę należy wypełnić wartościami 0, 1, 2 i tak dalej.
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jUstal rozmiar tabeli
Należy użyć siatki n+1 na m+1, aby puste prefiksy miały własny wiersz i kolumnę. To dopełnienie upraszcza pętle.
dp = [[0] * (m+1) for _ in range(n+1)]Wypełniaj w odpowiedniej kolejności
Należy iterować po i oraz j, zaczynając od 1. Każda komórka zależy wyłącznie od już wypełnionych sąsiadów z góry, z lewej i z przekątnej.
for i in range(1, n+1):
for j in range(1, m+1):
...Odczytaj odległość
Minimalna liczba operacji znajduje się w rogu. Odpowiedzią jest dp[n][m] po ukończeniu wypełniania tabeli.
distance = dp[n][m]Koszt i warianty
Algorytm działa w czasie O(n times m). W rzeczywistych zadaniach poszczególne operacje mogą mieć różne koszty, ale ta sama rekurencja nadal działa.
Szybkie sprawdzenie
Znaki A[i-1] i B[j-1] różnią się. Która rekurencja wyznacza odległość edycyjną?
Podsumowanie: odległość edycyjna
Zgodność oznacza przepisanie wartości z przekątnej, a niezgodność — 1 plus minimum z trzech sąsiadów. Należy zainicjalizować krawędzie i odczytać dp[n][m]. ✏️
Ucz się Python dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 30
- Lekcje
- 120
Często zadawane pytania
Czy lekcja „Odległość edycyjna krok po kroku” jest bezpłatna?
Tak — pełny tekst „Odległość edycyjna krok po kroku” 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 „Odległość edycyjna krok po kroku”?
Wstawianie, usuwanie i zastępowanie w celu przekształcenia Ć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 4 z 4.
Ile czasu zajmuje lekcja „Odległość edycyjna krok po kroku”?
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