Pitanje ili opis problema
Čini mi se da u ovom zadatku postoji greška u rešenju.
Induktivna hipoteza ne treba da bude
int r1 = dp[i-1][j] + cenaUmetanja;
int r2 = dp[i][j-1] + cenaBrisanja;
int r3 = dp[i-1][j-1] + cenaIzmene;
već
int r1 = dp[i-1][j] + cenaBrisanja;
int r2 = dp[i][j-1] + cenaUmetanja;
int r3 = dp[i-1][j-1] + cenaIzmene;
jer je ideja da ako svodimo dp[i][j] na dp[i-1][j] onda moramo prvo da izgubimo jedno slovo iz prve reči, pa da onda od prvih (i-1) slova prve reči pravimo prvih j slova druge reči. Pošto “gubimo” jedno slovo onda se dodaje cenaBrisanja, a ne cenaUmetanja.
Na primer, u test primeru 5
fyvrug
ywunxnr
4
6
9
zvaničan odgovor je 44 (2 umetanja, 3 brisanja i 2 promene), a edit distanca je zapravo 42: 3 umetanja (x, n i r), 2 brisanja (f i r) i 2 promene (v → w i g → n).