Two types of couting change problem (DP)

1. to minimize the number of coins

• NIT judge
  
• topCoder DP tutorial

d[i] = min(d[i], d[i - denomination[j]] + 1)
       j

e.g., coins = {1, 5, 10, 25}, 其实算到100以内足够了，100以上的(n > 100) 用
(n / 100) x 4 + d[n % 100] 就行了。(整dollar直接4个quarter, 零头查100以内的表)如果还要输出各种coin都用了多少，用个d[i][D] 二维表，第二维直接存各种coin用的数. 上面的例子，

           [0]   [1]  [2]  [3]  [4]
       0(min num) 1c  5c   10c 25c
-------+---------+---+----+----+---|
|d[1]  |      1  |  1|   0|   0|  0|
|d[2]  |      2  |  2|   0|   0|  0|
       ....
|d[5]  |      1  |  0|   1|   0|  0|
|d[6]  |      2  |  1|   1|   0|  0|
       ....
|d[100]|      4  |  0|   0|   0|  4| 

2. to output the maximum number of ways to count the changes
Uva judge:

• 147 Dollars,
• 674 Coin Change

"The number of ways to change amount A using N kinds of coins equals to:

• The number of ways to change amount A using all but the first kind of coins, plus
• The number of ways to change amount A-D using all N kinds of coins, where D is the denomination of the first kind of coin." --- Art of programming contest SE for uva