-
-
Notifications
You must be signed in to change notification settings - Fork 295
/
coin_change.rb
31 lines (27 loc) · 982 Bytes
/
coin_change.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def coin_change_minimum(coins, amount)
dp = Array.new(amount + 1, -1)
dp[0] = 0
coins.each do |coin|
(coin..amount).each do |i|
if dp[i - coin] != -1
dp[i] = -1 == dp[i] ? dp[i - coin] + 1 : [dp[i], dp[i - coin] + 1].min
end
end
end
dp[amount]
end
def coin_change_combinations(coins, amount)
dp = Array.new(coins.length + 1) { Array.new(amount + 1, 0) }
dp[0][0] = 1
(1..coins.length).each do |i|
(0..amount).each do |j|
dp[i][j] = dp[i - 1][j] + (j < coins[i - 1] ? 0 : dp[i][j - coins[i - 1]])
end
end
dp[coins.length][amount]
end
coins = Array[2, 4, 5]
amount = 12
puts 'Number of combinations of getting change for ' + amount.to_s + ' is ' + coin_change_combinations(coins,
amount).to_s + '.'
puts 'Minimum number of coins required for ' + amount.to_s + ' is ' + coin_change_minimum(coins, amount).to_s + '.'