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.