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.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
În problema monedelor, dp[s] e numărul minim de monede pentru suma s. Recurența: dp[s] = min(dp[s], dp[s - m] + 1) pentru fiecare monedă m. Pentru ca min să funcționeze, valoarea de pornire trebuie să fie mai mare decât orice răspuns posibil.
Cu dp = [0] * (suma + 1), fiecare min(0, ...) rămâne 0, deci funcția returnează 0 pentru orice sumă. Altă variantă a greșelii: pornești cu un număr „mare” prea mic (de exemplu 100) sau uiți să tratezi sumele imposibile, iar programul returnează infinitul sau valoarea de pornire ca răspuns.
Regula generală la DP: inițializarea trebuie să fie elementul neutru al operației. Pentru minim: infinit; pentru maxim: minus infinit; pentru numărări: 0, cu cazul de bază 1.
De ce apare: cauzele frecvente
1Tabelul de minim pornește de la 0
dp = [0] * (suma + 1)
for s in range(1, suma + 1):
for m in monede:
if m <= s:
dp[s] = min(dp[s], dp[s - m] + 1)dp = [float('inf')] * (suma + 1)
dp[0] = 0
for s in range(1, suma + 1):
for m in monede:
if m <= s:
dp[s] = min(dp[s], dp[s - m] + 1)Doar dp[0] = 0 e un caz de bază real. Restul sumelor sunt „imposibile” până găsim o combinație.
2Suma imposibilă nu e tratată
return dp[suma]return dp[suma] if dp[suma] != float('inf') else -1Dacă suma nu se poate forma, dp[suma] rămâne infinit. Enunțurile cer de obicei -1.
Repară eroarea, direct în pagină
Funcția rest_minim(monede, suma) calculează numărul minim de monede pentru o sumă, sau -1 dacă suma nu se poate forma. Testul cu assert pică: funcția returnează mereu 0. Repar-o ca testele să treacă și să afișeze 3, -1 și 0.
def rest_minim(monede, suma):
dp = [0] * (suma + 1)
for s in range(1, suma + 1):
for m in monede:
if m <= s:
dp[s] = min(dp[s], dp[s - m] + 1)
return dp[suma]
for monede, suma, corect in [([1, 2, 5], 11, 3), ([2], 3, -1), ([1], 0, 0)]:
rez = rest_minim(monede, suma)
assert rez == corect, f'rest gresit pentru {suma}: {rez}'
print(rez)3 -1 0
Indiciu
Pornește cu infinit pe toate pozițiile, dp[0] = 0, și returnează -1 dacă la final valoarea a rămas infinită.
Reparația
def rest_minim(monede, suma):
dp = [float('inf')] * (suma + 1)
dp[0] = 0
for s in range(1, suma + 1):
for m in monede:
if m <= s:
dp[s] = min(dp[s], dp[s - m] + 1)
return dp[suma] if dp[suma] != float('inf') else -1
for monede, suma, corect in [([1, 2, 5], 11, 3), ([2], 3, -1), ([1], 0, 0)]:
rez = rest_minim(monede, suma)
assert rez == corect, f'rest gresit pentru {suma}: {rez}'
print(rez)De ce merge
Cu tabelul plin de 0, fiecare min(dp[s], ...) păstra 0, deci orice sumă părea să se formeze cu zero monede. Infinitul înseamnă „încă nu știu cum se formează suma”, iar dp[0] = 0 e singurul caz de bază real. Pentru 11, DP-ul găsește 5 + 5 + 1; pentru 3 cu monede de 2, valoarea rămâne infinită, iar funcția returnează -1.
Cum o eviți pe viitor
Înainte să scrii bucla DP, scrie pe o linie ce înseamnă dp[i], cazul de bază și valoarea „nedefinit” (infinit pentru minim, minus infinit pentru maxim). Testează imediat trei cazuri: suma 0 (răspuns 0), o sumă imposibilă (răspuns -1) și un exemplu cunoscut. Dacă toate răspunsurile ies 0, aproape sigur e inițializarea.
Întrebări frecvente
Pot folosi suma + 1 în loc de infinit?
Da, e un truc des folosit: nu poți avea nevoie de mai mult de suma monede (cu moneda 1), deci suma + 1 înseamnă „imposibil” și rămâne întreg.
De ce nu merge greedy (cea mai mare monedă întâi)?
Pentru monede ca [1, 3, 4] și suma 6, greedy dă 4 + 1 + 1 (3 monede), dar optimul e 3 + 3 (2 monede). DP verifică toate variantele.
Erori înrudite
OverflowError: cannot convert float infinity to integer Încerci să transformi float('inf') într-un întreg, de obicei cu int() sau round() pe o distanță care a rămas infinită pentru că nodul nu poate fi atins. Verifică înainte dacă valoarea e infinită (math.isinf sau == float('inf')) și returnează -1 sau un mesaj. Rucsacul 0/1 cu tabel 1D parcurs crescător folosește același obiect de mai multe ori În rucsacul 0/1 cu un singur rând dp, dacă parcurgi capacitățile crescător, dp[w - g] e deja actualizat cu obiectul curent, deci obiectul e pus de mai multe ori. Parcurge capacitatea descrescător: for w in range(C, g - 1, -1). Kadane returnează 0 pentru o listă doar cu numere negative Ai pornit maximul (sau suma curentă) de la 0, iar când toate numerele sunt negative, nicio secvență nu trece de 0. Pornește de la primul element: cel_mai_bun = curent = nums[0], apoi curent = max(x, curent + x) pentru restul. Î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.
