Easy dynamic programming recursive formula (uva 147 coin change)

Question

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]]?

Answer 1

Ok, i found it on a website - same problem.

The coin change recurrence: a[i][j] = a[i-1][j] (d[i] > j) (If the coin can't be used, then don't use it)

a[i][j] = a[i-1][j] + a[i][j-d[i]] (d[i] <= j) (If the coin can be used: don't use OR use it)