9.8 Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.
這道題給定一個錢數，讓我們求用quarter，dime，nickle和penny來表示的方法總和，很明顯還是要用遞歸來做。比如我們有50美分，那麼
makeChange(50) =
makeChange(50 using 0 quarter) +
makeChange(50 using 1 quarter) +
makeChange(50 using 2 quarters)
而其中第一個makeChange(50 using 0 quarter)又可以拆分為：
makeChange(50 using 0 quarter) =
makeChange(50 using 0 quarter， 0 dimes) +
makeChange(50 using 0 quarter， 1 dimes) +
makeChange(50 using 0 quarter， 2 dimes) +
makeChange(50 using 0 quarter， 3 dimes) +
makeChange(50 using 0 quarter， 4 dimes) +
makeChange(50 using 0 quarter， 5 dimes)
而這裡面的每項又可以繼續往下拆成nickle和penny，整體是一個樹形結構，計算順序是從最底層開始，也就是給定的錢數都是由penny組成的情況慢慢往回遞歸，加一個nickle，加兩個nickle，再到加dime和quarter，參見代碼如下：
解法一：.
上述代碼雖然正确但是效率一般，因為存在大量的重複計算，我們可以用哈希表來儲存計算過程中的結果，下次遇到相同結果時，直接從哈希表中取出來即可，參見代碼如下：
解法二：