To practice Scala I wanted do solve simple dynamic programming exercises with Scala. For some exercises I already wrote a Python implementation. Using Python most of the time I saved the intermediate results in an array.
For example this Exercise:
The algorithm outputs the minimal amount of coins needed to reach a value, given the value and a list of coins. (Assuming there is an unlimited amount of coins.)
def automat(n, coins = [1,2,5,10,20,50,100,200]):
A = [0]
for i in range(1, n + 1):
smallest_change = min([A[i - coin] for coin in coins if 0 <= i - coin])
A.append(smallest_change + 1)
return A[n]
Looks very simple in Python. Nevertheless I have problems writing the same code in Scala. Because of the functional paradigm I did not want to use a for-loop, but rather a tail-recursive algorithm to solve that problem. And I couldn't find any good solution. Maybe a tail-recursive algorithm is not the right way to go and there is a different scala-way to implement this simple algorithm.
I already looked for scala implementation of dynamic programming exercises and couldn't find a good source yet. Has someone an idea what the scala way to implement this would look like?
UPDATE:
The closest I came so far is very similar to Dimas tail-recursive approach. It looks like this
def automat(n: Int, coins: List[Int] = List(1, 2, 5, 10, 20, 50, 100, 200)): Int = {
inner(n, n + 1, coins, List(0)).last
}
def inner(n: Int, m: Int, coins: List[Int], result: List[Int]): List[Int] = n match {
case 0 => result
case _ => inner(n-1, m, coins, result ::: List(coins.collect { case coin if (0 <= m - n - coin) => result(m - n - coin) }.min + 1))
}