Coin Change
ניתנת לך רשימה coins של ערכי מטבעות שונים ויעד amount. אפשר להשתמש בכל ערך של מטבע כמה פעמים שרוצים. יש להחזיר את המספר הקטן ביותר של מטבעות שסכום ערכיהם הוא בדיוק amount, או -1 אם אין שילוב של מטבעות שמגיע אליו. סכום של 0 דורש 0 מטבעות.
פונקציה
- coinsinteger-array
- ערכי המטבע השונים, שכל אחד מהם ניתן לשימוש בכל מספר של פעמים
- amountinteger
- הסכום הכולל שיש לשלם בדיוק
- מחזירהinteger
- מספר המטבעות הקטן ביותר הדרוש, או -1 אם אי אפשר להרכיב את הסכום
אילוצים
1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 1040 ≤ amount ≤ 104- כל ערכי המטבעות שונים.
דוגמאות
- קלט
- coins = [2, 5, 10]amount = 27
- פלט
- 4
- הסבר
- 10 + 10 + 5 + 2 נותנים 27 באמצעות ארבעה מטבעות. שלושה מטבעות לא מספיקים: 27 הוא אי־זוגי, ולכן צריך בדיוק מטבע אחד של 5, ושני האחרים מסתכמים לכל היותר ב־20, פחות מ־22.
- קלט
- coins = [4, 6]amount = 7
- פלט
- -1
- הסבר
- שני ערכי המטבעות זוגיים, ולכן כל סכום שתוכל להרכיב יהיה זוגי. 7 הוא אי־זוגי, ולכן התשובה היא -1.
- קלט
- coins = [3, 7]amount = 0
- פלט
- 0
- הסבר
- תשלום של 0 לא דורש מטבעות כלל, לכן התשובה היא 0, יהיו ערכי המטבעות אשר יהיו.
שאלת המשך
האם תוכל לספור כמה צירופים שונים של מטבעות מסתכמים ב־amount, במקום למצוא את מספר המטבעות הקטן ביותר?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
בחירה תמידית במטבע הגדול ביותר שמתאים לא תמיד נותנת את מספר המטבעות הקטן ביותר. נסו זאת עם המטבעות
[1, 3, 4]והסכום6.נניח שכבר ידעת את מספר המטבעות הקטן ביותר לכל סכום שקטן מ־
t. מאילו סכומים קטנים יותר אפשר להגיע ל־tעם מטבע אחד נוסף?מלאו טבלה
fewest[0..amount]החל מ־0כלפי מעלה:fewest[0] = 0, וכלfewest[t]הוא אחד יותר מהערך הטוב ביותר שלfewest[t - c]עבור המטבעותc <= t. סמנו סכומים שאי אפשר להגיע אליהם בערך גדול מכל תשובה אפשרית, כמוamount + 1, והמירו אותו ל־-1בסוף.
פתרון
בחירה במטבע הגדול ביותר שמתאים נכשלת: עם המטבעות 1, 3 ו־4, הסכום 6 משולם באמצעות 4 + 1 + 1, בעוד ש־3 + 3 דורשים שני מטבעות. מספר המטבעות המינימלי לסכום מסוים תלוי רק במספר המטבעות המינימלי לסכומים קטנים יותר, ולכן פותרים כל סכום מ־0 עד amount פעם אחת.
נסו כל שילוב באמצעות רקורסיה
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
אם המטבע האחרון ששילמת שווה ל־c, המטבעות שלפניו משלמים remaining - c בעלות הנמוכה ביותר האפשרית. לכן fewest(remaining) הוא אחד יותר מהערך הטוב ביותר של fewest(remaining - c) מבין כל המטבעות שמתאימים. כך נבדקת כל סדרה של מטבעות שאינה חורגת מהסכום, ולכן אי אפשר לפספס את האפשרות הטובה ביותר.
אותם סכומים נפתרים שוב ושוב. עם מטבעות בערכים 2, 5 ו־10, הסכום 27 מגיע ל־15 אחרי תשלום של 10 + 2, 2 + 10, 5 + 5 + 2 ועוד סדרים, ומחשב מחדש את 15 מההתחלה בכל פעם. מספר הקריאות גדל באופן מעריכי עם הסכום.
אלגוריתם
- כתבו פונקציית עזר
fewest(remaining)שמחזירה את מספר המטבעות הקטן ביותר עבורremaining, או -1 אם אין פתרון. - אם
remainingהוא 0, החזירו 0. - עבור כל מטבע שאינו גדול מ־
remaining, קראו לפונקציית העזר עם הסכום שנותר לאחר תשלום במטבע הזה. - שמרו את התוצאה הקטנה ביותר שאינה -1, והוסיפו לה 1 עבור המטבע ששילמתם.
- החזירו את המספר הזה, או -1 אם אף מטבע לא הוביל לפתרון. התשובה היא
fewest(amount).
def coinChange(coins, amount):
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
return best
return fewest(amount)רקורסיה עם ממוּזציה
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
הרקורסיה שואלת רק על סכומים מ־0 עד amount. שמרו כל תשובה במערך בפעם הראשונה שאתם מחשבים אותה, והחזירו את הערך השמור כשהסכום הזה מופיע שוב. כל סכום נפתר פעם אחת באמצעות לולאה שעוברת על המטבעות: עבודה בהיקף O(amount × coins).
הקריאות עדיין מקוננות ברמה אחת לכל מטבע שמשלמים. עם מטבע שערכו 1, מדובר בעד 10^4 רמות, יותר ממה שמחסנית הקריאות כברירת מחדל מאפשרת בשפות רבות.
אלגוריתם
- צרו מערך
memoעם מקום לכל סכום מ־0 עדamount, שיכיל סימון שפירושו שעדיין לא חושב. - ב־
fewest(remaining), החזירו 0 עבור 0, והחזירו אתmemo[remaining]אם כבר יש בו תשובה. - אחרת, נסו כל מטבע שמתאים, כמו ברקורסיה הפשוטה, ושמרו את התוצאה הקטנה ביותר בתוספת אחת.
- שמרו את התוצאה, כולל -1, ב־
memo[remaining]לפני שתחזירו אותה. - החזירו את
fewest(amount).
def coinChange(coins, amount):
# memo[r] holds the answer for r once it is worked out; None means not yet
memo = [None] * (amount + 1)
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
if memo[remaining] is not None:
return memo[remaining]
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
memo[remaining] = best
return best
return fewest(amount)תכנות דינמי מלמטה למעלה על פני סכומים
האינטואיציה
מלא טבלה fewest החל מ־0 כלפי מעלה. כשמגיעים לסכום t, כל סכום קטן יותר כבר טופל, ולכן fewest[t] הוא אחד יותר מהערך הקטן ביותר של fewest[t-c] מבין המטבעות c שמתאימים.
בסכומים שאי אפשר להגיע אליהם בשום שילוב של מטבעות מופיע הסמן amount + 1. הערך של כל מטבע הוא לפחות 1, ולכן תשובה אמיתית לעולם לא משתמשת ביותר מ־amount מטבעות, והסמן מפסיד בכל השוואה. לולאה מחליפה את הרקורסיה, ולכן לעומק מחסנית הקריאות אין שום חשיבות.
אלגוריתם
- צרו את
fewestעםamount + 1איברים, כשכולם מוגדרים לערך הסימוןamount + 1, והגדירו אתfewest[0]ל־0. - עבור כל סכום
tמ־1 עדamount, בדקו כל מטבעcשעבורוc ≤ t. - אם
fewest[t-c] + 1קטן מ־fewest[t], שמרו אותו ב־fewest[t]. - לאחר הלולאה, החזירו -1 אם
fewest[amount]עדיין מכיל את ערך הסימון, ואחרת החזירו אתfewest[amount].
def coinChange(coins, amount):
impossible = amount + 1
fewest = [0] + [impossible] * amount
for total in range(1, amount + 1):
for coin in coins:
if coin <= total and fewest[total - coin] + 1 < fewest[total]:
fewest[total] = fewest[total - coin] + 1
return fewest[amount] if fewest[amount] != impossible else -1
מלכודות ומקרי קצה
- בחירת המטבע הגדול ביותר תחילה. עם המטבעות 3 ו-5 וסכום של 9, משלמים 5 ו-3, נתקעים עם 1 ומחזירים -1, בעוד ש-3 + 3 + 3 עובד.
- שימוש במספר השלם הגדול ביותר כסמן. הוספת 1 אליו גורמת לגלישה למספר שלילי, שמנצח לאחר מכן בכל השוואה. השתמשו ב-
amount + 1. - הוספת 1 למבוי סתום. ענף שמחזיר -1, בתוספת המטבע ששילמתם, נותן 0 ומנצח בכל השוואה. דלגו על תוצאות של -1.
- רקורסיה בעומק של
amountרמות. עם מטבע שערכו 1 וסכום של10^4, Python נעצרת כברירת מחדל לאחר 1000 רמות, וגם JavaScript, Dart, Ruby ו-R אוזלות במחסנית. - קריאת
fewest[t-c]עבור מטבע שגדול מ-t, לפני תחילת הטבלה.
שאלות נפוצות3
למה הגישה החמדנית נכשלת בבעיית החלפת המטבעות?
בחירה במטבע הגדול ביותר שנכנס בסכום בטוחה רק במערכות מטבעות מסוימות, כמו רוב המטבעות האמיתיים. עם מטבעות בערכים 1, 3 ו־4 היא משלמת 6 בשלושה מטבעות במקום בשניים, ועם מטבעות בערכים 3 ו־5 היא אינה יכולה לשלם 9 כלל. תכנות דינמי משווה בין כל האפשרויות, ולכן שום מערכת מטבעות לא יכולה להטעות אותו.
מהי סיבוכיות הזמן של Coin Change?
פתרון התכנות הדינמי דורש זמן O(amount × coins) וזיכרון O(amount): רשומה אחת בטבלה לכל סכום, ובדיקה של כל מטבע עבור כל רשומה. רקורסיה פשוטה ללא שמירת תוצאות ביניים דורשת זמן מעריכי ביחס לסכום.
מה עדיף לבעיית החלפת המטבעות: מלמעלה למטה או מלמטה למעלה?
שתיהן מבצעות אותה כמות עבודה, O(amount × coins). רקורסיה מלמעלה למטה יכולה להגיע לעומק של הסכום, דבר שגורם לגלישת מחסנית הקריאות עבור 10^4 בכמה שפות. מלמטה למעלה ממלאת את הטבלה באמצעות לולאה, כך שאין לה מגבלת עומק והיא הבחירה הבטוחה יותר בריאיון.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def coinChange(coins, amount):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
coins = [2, 5, 10] amount = 27
הפלט הצפוי
4