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

Numărul de moduri de a da restul iese prea mare: DP-ul numără permutări, nu combinații

Pe scurt

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

Greșit
PYTHON
for s in range(1, suma + 1):
    for m in monede:
        if m <= s:
            dp[s] += dp[s - m]
Corect
PYTHON
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]

Greșit
PYTHON
dp = [0] * (suma + 1)
Corect
PYTHON
dp = [1] + [0] * suma

Există exact un mod de a forma suma 0: fără nicio monedă. Fără el, tot tabelul rămâne 0.

Repară tu

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.

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

Pune bucla peste monede în exterior și pe cea peste sume în interior, începând de la valoarea monedei.

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

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