Distanța de editare iese prea mică: prima linie și prima coloană din tabel nu sunt inițializate
dp[i][0] e costul transformării primelor i litere în textul gol, adică i ștergeri, iar dp[0][j] e j inserări. Dacă le lași 0, algoritmul crede că poți șterge sau insera gratuit. Inițializează dp[i][0] = i și dp[0][j] = j înainte de bucle.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
La distanța de editare (Levenshtein), dp[i][j] e numărul minim de operații (inserare, ștergere, înlocuire) prin care transformi primele i litere din a în primele j litere din b. Fiecare celulă depinde de vecinii de sus, din stânga și de pe diagonală, deci totul pornește de la marginile tabelului.
Marginile nu sunt 0: ca să transformi 'abc' în textul gol, ai nevoie de 3 ștergeri, deci dp[3][0] = 3. Ca să transformi textul gol în 'ab', ai nevoie de 2 inserări, deci dp[0][2] = 2. Dacă tabelul e creat cu zerouri și marginile nu sunt completate, recurența primește costuri prea mici, iar rezultatul final e prea mic. Pe distanta('abc', '') primești 0 în loc de 3.
Aceeași greșeală apare la orice DP pe două texte (cel mai lung subșir comun, potrivirea cu * și ?): cazurile de bază trebuie scrise explicit, nu lăsate pe seama valorii de inițializare.
De ce apare: cauzele frecvente
1Tabelul creat cu zerouri, fără margini
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
...dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i
for j in range(m + 1):
dp[0][j] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
...Marginile sunt cazurile de bază: i ștergeri, respectiv j inserări. Restul tabelului se construiește corect doar pornind de la ele.
2Recurența fără +1 pentru operație
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Doar când literele sunt egale treci gratuit pe diagonală. Altfel fiecare operație costă 1.
Repară eroarea, direct în pagină
Funcția distanta(a, b) calculează distanța de editare dintre două texte. Testul cu assert pică: pentru 'abc' și textul gol returnează 0. Repar-o ca să afișeze 3 (pentru 'kitten' și 'sitting') și 3 (pentru 'abc' și '').
def distanta(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[n][m]
r1 = distanta('kitten', 'sitting')
r2 = distanta('abc', '')
assert (r1, r2) == (3, 3), f'distanta gresita: {r1}, {r2}'
print(r1)
print(r2)3 3
Indiciu
Completează prima coloană cu i și primul rând cu j înainte de bucla principală.
Reparația
def distanta(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i
for j in range(m + 1):
dp[0][j] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[n][m]
r1 = distanta('kitten', 'sitting')
r2 = distanta('abc', '')
assert (r1, r2) == (3, 3), f'distanta gresita: {r1}, {r2}'
print(r1)
print(r2)De ce merge
Cu marginile lăsate 0, tabelul presupunea că transformi orice prefix în textul gol fără nicio operație, deci distanta('abc', '') returna direct dp[3][0] = 0, iar celelalte celule porneau de la costuri prea mici. dp[i][0] = i spune că ai nevoie de i ștergeri, iar dp[0][j] = j că ai nevoie de j inserări. Pornind de la aceste cazuri de bază, recurența dă valorile corecte: 3 pentru kitten și sitting.
Cum o eviți pe viitor
La orice DP, scrie întâi în cuvinte ce înseamnă o celulă (dp[i][j] = costul pentru primele i și primele j litere) și apoi completează cazurile de bază din această definiție. Testează mereu cu un text gol de o parte și de alta: distanta('abc', '') trebuie să fie 3, iar distanta('', 'ab') 2. Apoi un exemplu cunoscut, 'kitten' și 'sitting', cu răspunsul 3.
Întrebări frecvente
De ce indicii textului sunt i - 1 și j - 1?
Tabelul are un rând și o coloană în plus pentru textul gol, deci celula dp[i][j] corespunde literelor a[i-1] și b[j-1].
Pot folosi doar două rânduri în loc de tot tabelul?
Da, fiecare rând depinde doar de cel anterior, deci memoria scade la O(m). Și acolo, primul rând trebuie inițializat cu 0, 1, 2, ..., m, iar primul element al fiecărui rând nou cu i.
Erori înrudite
Restul minim cu monede iese 0: tabelul DP e inițializat cu 0 în loc de infinit La un DP de minim (cele mai puține monede), valoarea inițială trebuie să fie „imposibil” (float('inf')), nu 0, pentru că min(0, orice) rămâne 0. Pornește cu dp = [float('inf')] * (suma + 1), dp[0] = 0, iar la final returnează -1 dacă dp[suma] e tot infinit. IndexError: list index out of range la dp[n] (tabelul DP e prea scurt) Ai creat tabelul cu dp = [0] * n, dar răspunsul e dp[n], iar o listă cu n elemente are doar indicii 0..n-1. Când dp[i] înseamnă „primele i elemente” sau „treapta i”, tabelul are nevoie de n + 1 poziții: dp = [0] * (n + 1). Cel mai lung subșir crescător returnează dp[-1] în loc de max(dp) dp[i] e lungimea celui mai lung subșir crescător care se termină chiar la poziția i, nu cea mai bună din tot șirul. Răspunsul e maximul din tot tabelul: return max(dp, default=0), nu dp[-1]. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
