Skip to content

Instantly share code, notes, and snippets.

@peterwillcn
Created April 26, 2020 14:23
Show Gist options
  • Save peterwillcn/177c46463ec8822cd1a00e840cb751c0 to your computer and use it in GitHub Desktop.
Save peterwillcn/177c46463ec8822cd1a00e840cb751c0 to your computer and use it in GitHub Desktop.
Example of dynamic programming in Ruby
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