Monday, September 15, 2008

Two types of couting change problem (DP)

1. to minimize the number of coins

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:

"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