Coin Change

لديك عدد غير محدود من العملات المعدنية ذات قيم مختلفة قليلة، وتريد دفع مبلغ محدد باستخدام أقل عدد ممكن من العملات.

قد يبدو اختيار أكبر عملة لا يتجاوز مقدارها المبلغ مناسبًا، لكنه قد لا ينجح. باستخدام العملات [1, 3, 4] ومبلغ قدره 6، يؤدي اختيار أكبر عملة أولًا إلى 4 + 1 + 1، أي ثلاث عملات، بينما لا يتطلب 3 + 3 سوى عملتين.

الطريقة الأكثر أمانًا هي بناء الإجابة انطلاقًا من المبالغ الصغيرة. لتكن fewest[t] أقل عدد من العملات التي مجموعها t. دفع 0 لا يتطلب أي عملات. لأي قيمة أخرى من t، تكون قيمة العملة الأخيرة التي تستخدمها هي c، والمبلغ المتبقي قبل استخدامها هو t - c، لذا

fewest[t] = 1 + the smallest fewest[t - c] من بين كل عملة c لا تزيد قيمتها على t.

بالنسبة إلى [1, 3, 4]: fewest[3] = 1، وfewest[6] = 1 + fewest[3] = 2. إذا لم تؤدِّ أي عملة إلى مبلغ يمكن تكوينه، فلا يمكن دفع t على الإطلاق.

اكتب دالة باسم coinChange تستقبل coins، وهي قائمة بقيم عملات مميزة، وعددًا صحيحًا amount، وتُرجع أقل عدد من العملات التي مجموعها يساوي amount بالضبط. يمكنك استخدام كل قيمة عملة أي عدد من المرات. أرجِع -1 إذا تعذّر تكوين المبلغ، و0 عندما تكون قيمة amount هي 0.

على سبيل المثال، تُرجع coins = [2, 5, 10] وamount = 27 القيمة 4 (10 + 10 + 5 + 2)، بينما تُرجع coins = [4, 6] مع amount = 7 القيمة -1.

القيود: 1 <= coins.length <= 12, 1 <= coins[i] <= 10^4، جميع القيم مميزة، 0 <= amount <= 10^4.