How can I use dynamic programming in Scheme to solve the Coin Change problem?

Question

I'm trying to learn a Lisp language and have settled on Guile and am trying to solve this problem:

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Fundamentally, I understand the basic of dynamic programming where you can use recursion and memoization in order to save calculating at lower depths, but as Lisp I would expect it to be perfect for this type of problem. The problem I am having is returning separate lists for each combination of coins.

For an example case, consider target of 6 with coins [2, 3]. The simple tree would look like this:

The correct answer would be (3 3) with the other "complete" solution being (2 2 2).

However, if I try and construct these, the form I would want to use (without memoization) would look something like this.

(define get-coins (lambda (coins target) 
    (cond
        ((= target 0) '())
        ; not quite sure how to "terminate" a list here 
        ; An idea is to return (list -1) and then filter 
        ; lists that contain -1
        ((< target 0) ?????) 
        (else
            ; for each coin, recurse
            (map (lambda (v)
                (cons v (get-coins coins (- target v))))))
    )
))

However, this doesn't return more lists as it goes through. Rather, it creates nested lists. And this is my problem. Any help with this would be greatly appreciated.

Answer 1

I wanted to avoid nested lists, so I used a variable results:

(define (get-coins coins target)
  (let ((results '()))

Then I defined the function get-coins-helper, similar to your get-coins. And whenever I found some possible result, I used set! to update results:

 (letrec ((get-coins-helper
              (lambda (coins target result)
                (cond ((= target 0) (set! results (cons result results)))
                      ((< target 0) '())
                      (else (map (lambda (value)
                                   (get-coins-helper coins
                                                     (- target value)
                                                     (cons value result)))
                                 coins))))))

Then I called (get-coins-helper coins target '()) to find all possible results and at the end, I checked the value of results and returned -1 (if results are empty) or the shortest element of results:

      (if (null? results)
          -1
          (car (sort results (lambda (x y) (< (length x)
                                              (length y))))))

Full code:

(define (get-coins coins target)
  (let ((results '()))
    (letrec ((get-coins-helper
              (lambda (coins target result)
                (cond ((= target 0) (set! results (cons result results)))
                      ((< target 0) '())
                      (else (map (lambda (value)
                                   (get-coins-helper coins
                                                     (- target value)
                                                     (cons value result)))
                                 coins))))))
      (get-coins-helper coins target '())
      (if (null? results)
          -1
          (car (sort results (lambda (x y) (< (length x)
                                              (length y)))))))))

Some tests:

> (get-coins '(2 3) 6)
'(3 3)
> (get-coins '(2 3) 1)
-1