1require 'pp'
 2# https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/#!
 3
 4def coins(values, sum)
 5  min = Array.new(sum + 1, Float::INFINITY)
 6  min[0] = 0
 7
 8  for i in (0..sum)
 9    for j in (0..(values.size - 1))
10      break if values[j] > i
11      coin = values[j]
12
13      if min[i - coin] + 1 < min[i]
14        min[i] = min[i - coin] + 1
15      end
16    end
17  end
18  min.last
19end
20
21PP.pp coins([1, 3, 5], 11)