Problem 79 - 和の組合せ

メモ化の威力に感動した。

Problem 76 - PukiWiki

100の和の組合せを求める。両替問題のヤバいバージョン。

• ナイーブにやってみたら50で破綻した。
• 1だけの組合せになったら1種類と特殊化することで40秒で完了できるようになった。

同じ計算を何度もやってるので、そういう時はメモ化だろ！！と試してみたら。

(require (lib "69.ss" "srfi"))

(define (problem76 n)
  (letrec ((memoize (lambda (f)
                      (let ((table (make-hash-table)))
                        (lambda x
                            (or (and (hash-table-exists? table x)
                                     (hash-table-ref table x))
                                (let ((result (apply f x)))
                                  (hash-table-set! table x result)
                                  result))))))
           (iter
             (memoize
               (lambda (n l)
                 (cond ((or (zero? n) (= l 1)) 1)
                       ((or (negative? n) (zero? l)) 0)
                       (else
                         (+ (iter n (- l 1))
                            (iter (- n l) l))))))))
    (iter n (- n 1))))

(time (problem76 100))
; cpu time: 9 real time: 9 gc time: 0
; 190569291

0.01秒で終わった。

メモ化凄すぎ。