מריה בוטוסוב

נותנים מערך של מטבעות הקיימות ומטבע שצריך לפרוט. יש למצוא כמה דרכים אפשריים קיימים לעשות זה.

הבעיה היא מסוג תיכנות דינמי.

נגיד אנחנו צריכים לפרוט מטבע של 10 ש"ח ומטבעות האפשריות הן 1,5,10,25

נעשה טבלה:

amount/ כמות (מ - 0 עד למטבע)	10	9	8	7	6	5	4	3	2	1	0
דרכים עם מטבע 1	1	1	1	1	1	1	1	1	1	1	1
דרכים עם מטבע 5	3	2	2	2	2	2
דרכים עם מטבע 10	4

התוצא היא 4.

אלגוריטם:

public int WaysToChange(int n, int[] denoms) {
    int ways = new int[n+1];
    ways[0] = 1;
    foreach(int denom in denoms) {
        for(int amount = 1; amount < n+1; amount++) {
            if(denom <= amount) 
                ways[amount]+=ways[amount-denom];//formula - see table
        }
    }
}