În câte moduri poți da restul
Lecția trecută ai căutat numărul minim de monede. Acum numeri câte combinații diferite de monede formează suma. Capcana clasică de interviu: să nu numeri de mai multe ori aceeași combinație în altă ordine (1 + 2 și 2 + 1).
Problema
Primești suma și lista monede (oricâte bucăți din fiecare). Câte combinații distincte formează suma? Ordinea monedelor nu contează.
Scrie funcția moduri_rest(suma, monede) care returnează numărul de combinații de monede ce formează suma, cu un tabel DP în care bucla pe monede este în exterior. Testele sunt deja scrise.
- Creează dp = [0] * (suma + 1) și pune dp[0] = 1.
- Pentru fiecare monedă m, pentru s de la m la suma: dp[s] += dp[s - m].
- Returnează dp[suma]. Trebuie să apară: 4, 0, 1, 292.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Programare dinamică și interviuri simulate.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan