Numărul minim de monede pentru un rest
Un automat de cafea trebuie să dea restul cu cât mai puține monede. Pare simplu: dai mereu cea mai mare monedă posibilă. Asta merge pentru monedele românești, dar nu merge pentru orice sistem de monede. Programarea dinamică dă răspunsul corect mereu.
Problema
Primești lista monede (valori distincte, ai oricâte bucăți din fiecare) și o suma. Returnează numărul minim de monede cu care se formează suma, sau -1 dacă suma nu se poate forma.
Scrie funcția monede_minime(monede, suma) care returnează numărul minim de monede pentru suma sau -1 dacă suma nu se poate forma, cu un tabel DP. Testele sunt deja scrise.
- Creează tabelul dp de lungime suma + 1, plin cu infinit (math.inf sau suma + 1), și pune dp[0] = 0.
- Pentru fiecare sumă și fiecare monedă care încape, încearcă dp[s - m] + 1.
- Returnează -1 dacă dp[suma] a rămas infinit. Trebuie să apară: 3, -1, 2, 0.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Programare dinamică și interviuri simulate.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan