0

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