; coin change, part 2
(define (make-matrix rows columns . value)
(do ((m (make-vector rows)) (i 0 (+ i 1)))
((= i rows) m)
(if (null? value)
(vector-set! m i (make-vector columns))
(vector-set! m i (make-vector columns (car value))))))
(define (matrix-ref m i j) (vector-ref (vector-ref m i) j))
(define (matrix-set! m i j x) (vector-set! (vector-ref m i) j x))
(define (count coins n)
(let* ((k (vector-length coins))
(c (make-matrix k (+ n 1) 0)))
(do ((j 0 (+ j 1))) ((< n j))
(matrix-set! c 0 j j))
(do ((i 1 (+ i 1))) ((= i k))
(do ((j 1 (+ j 1))) ((< n j))
(matrix-set! c i j
(if (< j (vector-ref coins i))
(matrix-ref c (- i 1) j)
(min (matrix-ref c (- i 1) j)
(+ 1 (matrix-ref c i
(- j (vector-ref coins i)))))))))
(matrix-ref c (- k 1) n)))
(define (coins cs n)
(let* ((k (vector-length cs))
(c (make-matrix k (+ n 1) 0)))
(do ((j 0 (+ j 1))) ((< n j))
(matrix-set! c 0 j j))
(do ((i 1 (+ i 1))) ((= i k))
(do ((j 1 (+ j 1))) ((< n j))
(matrix-set! c i j
(if (< j (vector-ref cs i))
(matrix-ref c (- i 1) j)
(min (matrix-ref c (- i 1) j)
(+ 1 (matrix-ref c i
(- j (vector-ref cs i)))))))))
(let loop ((i (- k 1)) (j n) (zs (list)))
(cond ((and (zero? i) (zero? j)) zs)
((zero? i) (loop i (- j 1) (cons 1 zs)))
((= (matrix-ref c i j) (matrix-ref c (- i 1) j))
(loop (- i 1) j zs))
(else (loop i (- j (vector-ref cs i))
(cons (vector-ref cs i) zs)))))))
(display (count '#(1 5 10 25) 40)) (newline)
(display (coins '#(1 5 10 25) 40)) (newline)