换硬币问题

问题

给了 50 美分，25 美分，10 美分，5 美分，1 美分的硬币，将 1 美元换成零钱，一共有多少种不同的方式？

思想

总的方式 = 总的方式（有 50 美元）+ 总的方式（除了 50 美元），以 50 美元为例

子问题的边界情况：
总的方式（现金 a 换成 n 种硬币）= 总的方式（现金 (a - 50) 换成 n 种硬币）+ 总的方式（现金 a 换成 n-1 种硬币），以 50 美元为例
稍微抽象一下就是：总的方式（现金 a 换成 n 种硬币）= 总的方式（现金 a - d 换成 n 种硬币）+ 总的方式（现金 a 换成 n-1 种硬币）
开始边界：a = 100, n = 5
结束边界：

• a = 0, 表示的意思是所有的钱正好都换完，所以算是 1 种换零钱的方式。 如果打算写个通用的程序，比如说初始 a = 100 不固定，那么 a = 0 也可能是我本来就没钱，所以应该算是 0 种换零钱的方式
• a < 0, 表示的意思是最后剩下的钱不够换，所以算是 0 种换零钱的方式
• n = 0, 表示的意思是可以换的硬币有 0 种，所以算是 0 种换零钱的方式

代码

(define (cc a n)                        ; 总的方式（现金 a 换成 n 种硬币）
  (cond ((= a 0) 1)                     ; 边界, a=0
        ((or (< a 0) (= n 0)) 0)        ; 边界, a<0 和 n = 0
        (else (+ (cc (- a (d n)) n)     ; 总的方式（现金 a - d 换成 n 种硬币）
                 (cc a (- n 1))))))     ; 总的方式（现金 a 换成 n - 1 种硬币）

;方便理解，假设如下
;可换 5 种硬币 (n = 5), 那么假设需要除去 50 美分，所以 d = 50
;可换 4 种硬币，那么假设需要除去 25 美分，所以 d = 25
;...
;既然是假设，那么如下假设也是一样的
;(define (d n)
;  (cond ((= n 1) 50)
;        ((= n 4) 25)
;        ((= n 2) 10)
;        ((= n 3) 5)
;        ((= n 5) 1)))
(define (d n)
  (cond ((= n 5) 50)
        ((= n 4) 25)
        ((= n 3) 10)
        ((= n 2) 5)
        ((= n 1) 1)))

(define (count-change a)
  (cc a 5))         ; 边界, 有 5 种硬币

(count-change 100)  ; 边界, 有 100 美分