<prompt> Unapewa safu kamili sarafu zinazowakilisha sarafu za madhehebu tofauti na kiasi kamili kinachowakilisha jumla ya pesa.Rejesha _idadi chache zaidi za sarafu unazohitaji kutengeneza kiasi hicho_. Ikiwa kiasi hicho cha pesa hakiwezi kujumuishwa na mchanganyiko wowote wa sarafu, rudisha -1.Unaweza kudhani kuwa una idadi isiyo na kikomo ya kila aina ya sarafu.Mfano wa 1:Ingizo: sarafu 1,2,5, kiasi 11Pato: 3Maelezo: 11 5 5 1Mfano wa 2:Ingizo: sarafu 2, kiasi 3Pato: -1Mfano wa 3:Ingizo: sarafu 1, kiasi 0Pato: 0Vikwazo: 1 sarafu.urefu 12 1 sarafui 231 - 1 0 kiasi 104  <response>: chatudef coinChangesarafu, kiasi: dp kiasi 1 kiasi 1 dp0 0 kwa sarafu katika sarafu: kwa i katika anuwai sarafu, kiasi 1: dpi mindpi, dpi - sarafu 1 rudisha dpkiasi ikiwa dpkiasi kiasi kingine -1maelezoAlgorithm hapa inategemea upangaji wa nguvu. Tunaunda safu dp yenye fahirisi kutoka 0 hadi jumla ya kiasi tunachohitaji kulenga. Tunaanzisha safu ya dp kwa thamani kubwa kuliko kiasi kiasi 1. Hii ni kwa sababu thamani hii haiwezi kufikiwa kwa kutumia sarafu, na uanzishaji unahakikisha kwamba kila mara tunapata idadi halali ya chini ya sarafu.Tunaanza kwa kuanzisha dp0 hadi 0 kwani kutakuwa na sarafu 0 zinazohitajika kufanya jumla ya 0.Kisha, tunarudia kupitia safu ya sarafu iliyotolewa na kwa kila sarafu, tunaanza kurudia nyingine kutoka kwa thamani ya sarafu hadi jumla ya kiasi. Kwa kila faharasa i katika kitanzi hiki cha ndani, tunasasisha dpi kama kiwango cha chini zaidi cha thamani yake ya sasa dpi na dpi - coinsj 1. Hii inahakikisha kwamba tunapata idadi ya chini zaidi ya sarafu zinazohitajika kuunda jumla ya kiasi.Baada ya marudio haya, ikiwa thamani katika dpkiasi ni chini ya au sawa na kiasi kinacholengwa, tunarudisha thamani kama idadi ya chini zaidi ya sarafu inayohitajika. Vinginevyo, ikiwa ni kubwa kuliko kiasi, inamaanisha kuwa hatukuweza kupata mchanganyiko wa sarafu ili kufanya jumla ya kiasi, kwa hivyo tunarudi -1. 