בעיית החלפת מטבעות

בעיית החלפת המטבעות היא בעיה קלאסית בתכנות דינמי. בהינתן קבוצת מטבעות בערכים שונים וסכום כסף כולל, המשימה היא למצוא את מספר המטבעות המינימלי הדרוש להרכבת הסכום הנתון.

לדוגמה, נניח שיש לנו מטבעות בערכים [1, 5, 10] ואנחנו רוצים להרכיב את הסכום 15. מספר המטבעות המינימלי הדרוש יהיה 2 (מטבע של 10 ומטבע של 5).

כדי לפתור את הבעיה באמצעות תכנות דינמי, נוכל ליצור טבלה שבה השורות מייצגות את ערכי המטבעות והעמודות מייצגות את הסכומים מ-0 ועד לסכום הכולל הנתון. לאחר מכן נמלא את הטבלה מלמטה למעלה, על ידי חישוב מספר המטבעות המינימלי הדרוש להרכבת כל סכום, באמצעות המטבעות מכל ערך.