schemedynamic-programmingcoin-changeguile# How can I use dynamic programming in Scheme to solve the Coin Change problem?

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.

Solution

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
```

- Reverse the digits of a number using a list
- Exercise 12.10 from the book Scheme and the art of programming
- How to create Alist from List using syntax-rules in Scheme?
- Anonymous lambdas directly referring to themselves
- Why can't a Scheme macro with the name "if" be defined?
- How to implement "if" in normal order in Scheme?
- Map-reduce functional outline
- How to use let-values in Gambit Scheme?
- Execute command line from Scheme (Guile)
- How do I define a sub environment in scheme?
- Sources for learning about Scheme Macros: define-syntax and syntax-rules
- What is "Call By Name"?
- DrRacket's call/cc
- Racket: Conditional Statements Not Matching String Equality in Gambling Simulation"
- What's wrong with this coin change python implementation?
- Encode "ä", "ö", "ü" and "ß" in scheme (get german text from file)
- Using AND with the apply function in Scheme
- Combination of list-ref and index-of in racket
- How to undefine a variable in Scheme?
- Running Scheme from the command line
- Function that splits word
- How does the yin-yang puzzle work?
- Dr Racket Recursing Without Returning Inital Parent Node Within Function
- Chez Scheme FFI Procedure Doesn't Work After Change to Apple Silicon
- How do we convert this Scheme (Lisp) function into C#
- What is #~ in scheme?
- Racket : Run scheme file in terminal and show result
- Recursive numeric equality in Scheme
- Under any Scheme standard, is (let (x y z) x) valid code?
- Iterate through the letters of the alphabet in Racket