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

Restul minim cu monede iese 0: tabelul DP e inițializat cu 0 în loc de infinit

Pe scurt

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

Greșit
PYTHON
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)
Corect
PYTHON
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ă

Greșit
PYTHON
return dp[suma]
Corect
PYTHON
return dp[suma] if dp[suma] != float('inf') else -1

Dacă suma nu se poate forma, dp[suma] rămâne infinit. Enunțurile cer de obicei -1.

Repară tu

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.

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

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

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