```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 ``` ```; 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) ```
 ```1 2 ``` ```3 (5 10 25) ```