[UVA] 166 Making Change

錢幣組合一直是我的痛。我會DP，但是只要是錢幣題一定會搞我至少半天。這次也一樣。一個簡單的DP題，因為沒有check array index out of bound就搞了我一個小時。唉。

作法就是建兩個DP table，即金額對最少的錢幣數量。一個是店家用的shop_table，一個是顧客用的customer_table。注意店家的table 可以重復用，但是顧客的table每從都要regenerate，而且還 個別錢幣還有數量限制。

再由 Pay - Cost = Return
所以 coin_number[Cost] = min (customer_table[Pay] + shop_table[Pay - Cost]) Pay從Cost試到Cost + $1.95即可。

有用的測資：


2 2 2 2 2 1 4.05
2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55
0 5 1 0 1 9 1.55
0 5 5 1 6 1 3.75
7 8 4 5 1 7 2
8 0 3 3 7 8 1.65
0 0 6 7 8 0 3.15
0 0 0 0 0 0