*Coin Change problem
     Suppose that we have the following coins:
     1 cent (penny), 5 cent (nickle), 10 cent (dime), 25 cent (quarter)

     如何把要找的錢用最少的 coins 組成?
     For example, 63 cents ?
  Greedy method 就是先選目前看起來最好的 (locally optimal)
    --> 要最少 coin, 當然先選值大的 --> 25 cent * 2 = 50 cents
        63 - 50 = 13  -->  選可用的最大 10 cent
        13 -10 = 3  -->  只好選 3 個 1 cent 的
       ===> 共有 2 個 25cent, 1 個 10cent, 3 個 1 cent
       ===> 在此例中就是最佳解


==== ===>但, 雖然 Greedy 一定可以找到 feasiable solution
         可是, 有時候 Greedy 方法不一定能找到 optimal solution!
             (i.e., 有解, 但不是最佳)
         例: 如果有 21 cent coin
             則顯然最佳解應該是 3 個 21 cent coin 就共 63 cents
           此時要用 Dynamic Programming 技巧


*Dynamic programming 的主要精神是:
 * Divide and conquer 
 * recursive
 * 用table或是 array 記住以前算過的答案以節省 recursive 次數 (最重要)

   以這個 找零錢 為例子:
     要找出 63 cents 最少要多少 銅板 ==>
       -->   找 best(1 + 62, 2+61, 3+60, 4+59, 5+58, ..., 31+32)
           ...
      因為會用 array 把 1, 2, 3, 4, 5 cent, ... 的最佳解記住
      所以 recursive 不會很深