Easy dynamic programming - uva 147 ,

[kenjegalee]

the problem is about coin change - "how many ways you can change 3,5,10 dollars if you have 5c,10c ......

"http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=83

the problem is solved many times on various blogs( solution here )

In dp, the hardest thing is to understand the relation between subproblems and get the formula(optimal substructure)

I only give the actual for loop that stores the ways into 2d table like the solution:

for (int i = 2; i <= NCHANGES; ++i){
      for (int m = 1; m <= MAX_AMOUNT; ++m){
          if (m >= coins[i])
            n[i][m] = n[i-1][m] + n[i][m - coins[i]];
          else  n[i][m] = n[i-1][m];
}
}

=================================

The actual important code:

 **if (m >= coins[i])
        n[i][m] = n[i-1][m] + n[i][m - coins[i]];
      else
        n[i][m] = n[i-1][m];**

My thinking.

for example: (else case)

• I have the amount 5 cents and 1 coin to use : 5c. there is only 1 way : 5c = 1 * 5c (store n[5][coin(5)])
• I have the amount 5c and 2 coins to use : 5c and 10c i can't use BOTH 5C and 10c => i go back to 1 WAY of doing it ( store 1 in the table for n[5][coin(5,10)]) for this case

that's why n[i][m] = n[i-1][m]

can you explain the first if case? n[i][m] = n[i-1][m] + n[i][m - coins[i]]?

[sepp2k]

Let's say you have 25c and can use the 10c and 5c coins. Since 15 is greater than 10, you may use a 10c coin. If you do, you have 15c left (for which you again may or may not use another 10c coin). If you don't, you still have 25c left, which you pay with 5c coins.

So the total number of ways to give change for 25c using 10c and 5c coins is the number of ways you can give change for 25c using only 5c coins (n[0][25]) plus the number of ways you can give change for 15c using 10c and 5c coins (n[1][15]).