Numărul de moduri de a da restul iese prea mare: DP-ul numără permutări, nu combinații
Dacă bucla exterioară e peste sume și cea interioară peste monede, 1 + 2 și 2 + 1 sunt numărate separat. Pentru combinații, pune monedele în bucla exterioară: for m in monede: for s in range(m, suma + 1): dp[s] += dp[s - m].
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Problema „în câte moduri poți forma suma S din monede” are două variante: combinații (ordinea nu contează: 1 + 2 și 2 + 1 sunt același mod) și permutări (ordinea contează, ca la urcatul treptelor). Codul e aproape identic, iar diferența e doar ordinea celor două bucle.
Cu sumele în exterior, dp[s] adună, pentru fiecare monedă, toate modurile de a forma restul, inclusiv cele care folosesc monede „mai mari” înainte. Așa apar toate ordinile posibile. Cu monedele în exterior, fiecare monedă e adăugată după cele de dinainte, deci fiecare combinație apare o singură dată, într-o ordine fixă.
Nu primești nicio eroare, doar un număr mai mare decât cel așteptat. Pentru suma 4 cu monede [1, 2] corect e 3, iar varianta greșită dă 5.
De ce apare: cauzele frecvente
1Buclele inversate
for s in range(1, suma + 1):
for m in monede:
if m <= s:
dp[s] += dp[s - m]for m in monede:
for s in range(m, suma + 1):
dp[s] += dp[s - m]Cu monedele în exterior, combinațiile se construiesc într-o ordine fixă a monedelor, deci nu se repetă.
2Inițializarea lui dp[0]
dp = [0] * (suma + 1)dp = [1] + [0] * sumaExistă exact un mod de a forma suma 0: fără nicio monedă. Fără el, tot tabelul rămâne 0.
Repară eroarea, direct în pagină
Funcția moduri(suma, monede) trebuie să numere în câte moduri poți forma suma, fără să conteze ordinea monedelor. Testul cu assert pică: rezultatele sunt prea mari. Repar-o ca să afișeze 4, 3 și 0.
def moduri(suma, monede):
dp = [1] + [0] * suma
for s in range(1, suma + 1):
for m in monede:
if m <= s:
dp[s] += dp[s - m]
return dp[suma]
for suma, monede, corect in [(5, [1, 2, 5], 4), (4, [1, 2], 3), (3, [2], 0)]:
rez = moduri(suma, monede)
assert rez == corect, f'moduri gresite: {rez} in loc de {corect}'
print(rez)4 3 0
Indiciu
Pune bucla peste monede în exterior și pe cea peste sume în interior, începând de la valoarea monedei.
Reparația
def moduri(suma, monede):
dp = [1] + [0] * suma
for m in monede:
for s in range(m, suma + 1):
dp[s] += dp[s - m]
return dp[suma]
for suma, monede, corect in [(5, [1, 2, 5], 4), (4, [1, 2], 3), (3, [2], 0)]:
rez = moduri(suma, monede)
assert rez == corect, f'moduri gresite: {rez} in loc de {corect}'
print(rez)De ce merge
Cu sumele în exterior, pentru suma 3 se numărau și 1 + 2, și 2 + 1, deci suma 5 dădea 9 în loc de 4. Când monedele sunt în exterior, întâi formezi toate sumele doar cu monede de 1, apoi adaugi monede de 2 peste ele și așa mai departe. Fiecare combinație apare o singură dată, cu monedele în ordine crescătoare.
Cum o eviți pe viitor
Când citești enunțul, decide dacă ordinea contează. Dacă nu („combinații”, „moduri de a da restul”), monedele merg în bucla exterioară; dacă da („secvențe”, „în câte feluri urci”), sumele merg în exterior. Verifică pe un exemplu mic, numărat de mână: suma 4 cu [1, 2] are 3 combinații (1111, 112, 22) și 5 permutări.
Întrebări frecvente
Și varianta cu tabel 2D?
dp[i][s] = moduri de a forma s cu primele i monede numără combinații. Varianta 1D cu monedele în exterior e aceeași idee, cu memorie mai puțină.
Merge la fel pentru rucsac 0/1?
Nu chiar. La rucsacul 0/1 fiecare obiect se folosește o singură dată, deci suma se parcurge descrescător. Aici monedele se pot repeta, deci se parcurge crescător.
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. 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). Memo greșit: cheia nu conține toți parametrii, iar rezultatul e greșit Ai salvat în memo rezultatul doar după i (memo[i]), dar funcția depinde și de alt parametru (capacitate, j, suma rămasă), așa că un rezultat calculat pentru o stare e refolosit pentru alta. Cheia memo-ului trebuie să conțină toți parametrii care schimbă rezultatul: memo[(i, capacitate)]. Î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.
