...
Eroare Algoritmi și structuri de date · Programare dinamică și memoizare

Distanța de editare iese prea mică: prima linie și prima coloană din tabel nu sunt inițializate

Pe scurt

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

Greșit
PYTHON
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        ...
Corect
PYTHON
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

Greșit
PYTHON
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
Corect
PYTHON
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ă tu

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 '').

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
3
3
Indiciu

Completează prima coloană cu i și primul rând cu j înainte de bucla principală.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.