Change money problem in Ruby (Dynamic Programming)

change_money_dp_in_ruby.md

As we already know, a natural greedy strategy for the change problem does not work correctly for any set of denominations. For example, if the available denominations are 1, 3, and 4, the greedy algorithm will change 6 cents using three coins (4 + 1 + 1) while it can be changed using just two coins (3 + 3). Your goal now is to apply dynamic programming for solving the Money Change Problem for denominations 1, 3, and 4.

Input Format.

Integer money.

Output Format.

The minimum number of coins with denominations 1, 3, 4 that changes money.

result = gets.chomp.to_i
coins = [1,3,4]
all_minimums = {}

for m in 0..result do
  local_min = 0
  previous_min = {}
  coins.each do |coin|
    if m >= coin # only if the exchangeable amount is greater than or equal to the face value of the coin
      previous_min[m - coin] = all_minimums[m - coin]
      min = previous_min.values.min
      local_min = min + 1
    end
  end

  all_minimums[m] = local_min
end

puts local_min