Skip to content

Instantly share code, notes, and snippets.

@peterwillcn

peterwillcn/change.rb

Created April 26, 2020 14:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save peterwillcn/177c46463ec8822cd1a00e840cb751c0 to your computer and use it in GitHub Desktop.
Save peterwillcn/177c46463ec8822cd1a00e840cb751c0 to your computer and use it in GitHub Desktop.
Download ZIP
Example of dynamic programming in Ruby
Raw
change.rb
INFINITY = 1.0/0
@changes = {}
@coins = [1, 3, 4]
def change(target_value)
return 0 if target_value == 0
return INFINITY if target_value < 0
@changes[target_value] ||= @coins.map do |coin|
change(target_value - coin) + 1
end.min
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment