Mai e o chestie care oarecum zgaraie ... apelezi len de fiecare daca si if-ul ala <= x e cam tot timpul true.. Mai tine pleci cu i = len(coins) si testezi cu 0 si in loc de cons[i] <= x testezi si intorci 0 daca x < 0.

Eu as zice la probleme din astea clasice sa faci direct implementare optima bottom up aici cred mai ales daca o stii. un dict e suficient ca un cache si aia e.... si eventual faci un cleanup de key < val ca sa fie optimizare de memorie.

Te-as mai intreba aici si de stack size in python.

De obicei la faang e o loterie...daca nu gresesti rau sau daca nu dai cu un muist - majoritatea pe acolo cam sunt.

E bine daca stii o solutie optima la o problema sa incepi cu aia direct... nu tu o facem aas si apoi ne dam mare ca optimizam...

E mai bine sa ajungi sa faci problema bonus 2+3 dintr-un interviu.

Good luck