练习1.14

 (define (count-change amount) 
   (cc amount 5)) 
 (define (cc amount kinds-of-coins) 
   (cond ((= amount 0) 1) 
         ((or (< amount 0) (= kinds-of-coins 0)) 0) 
         (else (+ (cc amount 
                      (- kinds-of-coins 1)) 
                  (cc (- amount 
                         (first-denomination kinds-of-coins)) 
                      kinds-of-coins))))) 
 (define (first-denomination kinds-of-coins) 
   (cond ((= kinds-of-coins 1) 1) 
         ((= kinds-of-coins 2) 5) 
         ((= kinds-of-coins 3) 10) 
         ((= kinds-of-coins 4) 25) 
         ((= kinds-of-coins 5) 50)))

图请参照SICP解题集 练习1.14

orz等我学会了LaTeX就自己画一个

时间复杂度大概是指数？或者高阶多项式？ 空间复杂度大概是线性？或者O(nlogn)？

递归算法我也不会证... 而且网上貌似也没有一个统一的说法

参考：

• http://wiki.drewhess.com/wiki/SICP_exercise_1.14
• http://alienshaw.lofter.com/post/a9f3a_1fac72
• http://blog.csdn.net/keyboardota/article/details/10565429

讲道理这道题是动态规划的基础题 优化的话用记忆化或者自底向上后时间复杂度就能成为O(amount * kinds-of-coins) 不过感觉scheme比较难写那就先不写了 有时间再仔细琢磨琢磨补上吧