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