# Swift Algorithm Club: June Digest 2017

The Swift Algorithm Club is happy to introduce three new algorithms this month: Minimum Coin Change, Minimum Spanning Tree, and Dijkstra's Algorithm!

This is a companion discussion topic for the original entry at https://www.raywenderlich.com/554-swift-algorithm-club-june-digest-2017

Hi, I am looking at the dynamic programming algorithm for the minimum coin problem which I feel can be improved.

First you don’t have to do recursion to do dynamic programming.

Second you can treat this particular case as a shortest path and as a data structure store as an array of what was the last coin used to reach that value.

``````public func noRecursion(_ value: Int) throws -> [Int] {

guard value > 0 else { return [] }
var foundMoneyValues  = Array(repeating: 0, count: value+1)
var currentSet:[Int] = []

for coin in sortedCoinSet {
if coin < value {
foundMoneyValues[coin] = coin
currentSet.append(coin)
} else if coin == value {
return [coin]
}
}

while !(currentSet.isEmpty) {
var nextSet:[Int] = []
for reachedAmount in currentSet {

for coin in sortedCoinSet {

let nextAmount = reachedAmount + coin
if nextAmount < value {

if foundMoneyValues[nextAmount] < 1 {
foundMoneyValues[nextAmount] = coin
nextSet.append(nextAmount)
}

} else if nextAmount == value {
var listOfCoinsToReturn = [coin]
var remaingValue = reachedAmount
while remaingValue > 0 {
let coinUsed = foundMoneyValues[remaingValue]
listOfCoinsToReturn.append(coinUsed)
remaingValue -= coinUsed
}
return listOfCoinsToReturn
}
}
}
currentSet = nextSet

}

throw MinimumCoinChangeError.noRestPossibleForTheGivenValue

}
``````

}