The Swift Algorithm Club is happy to introduce three new algorithms this month: Minimum Coin Change, Minimum Spanning Tree, and Dijkstra's Algorithm!
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
}
}