Effective way to memoize a combination of two numbers

Question

I'm working on an algorithm to count the number of ways to build 100 cents given an infinite amount of pennies, dimes, nickels, and quarters.

I ended up coming with the above (which AFAIK works):

def count_ways(amount)
  num_ways(amount, 0)
end

def num_ways(amount, index)
  return 1 if amount == 0
  return 0 if index >= COINS.length || amount < 0
  num_ways(amount - COINS[index], index) +
  num_ways(amount, index + 1)
end

Now, I'd like to memoize this algorithm. An effective way I've found to think about memoizing is to consider what inputs do we pass into this function repeatedly. In this case, I'd like to memoize the combination of amount & index parameters.

Typically when I have two parameters, I build a two D array as a way to memoize but here that makes a lot less sense. Consequently, how can you memoize off of these two parameters? Does it make sense to do something like this?

def count_ways(amount)
  memo = Hash.new { |h, k| h[k] = [] }
  num_ways(amount, 0, memo)
end

def num_ways(amount, index, memo)
  return 1 if amount == 0
  return 0 if index >= COINS.length || amount < 0
  memo[amount - COINS[index], index] ||= num_ways(amount - COINS[index], index)
  memo[amount, index + 1] ||= num_ways(amount, index + 1)

  memo[amount - COINS[index], index] +
    memo[amount, index + 1]
end

Answer 1

I believe there is no common way to implement memoization when you solve algo task. Because of speed. Way you have to choose depends on you algo, input data and so on. Few imperative rules:

• avoid creation of many data structure instances: h = {}; h[ [1,2] ] = 3 will produce COINS.size * amount Arrays just for keys
• use Array for contiguous data and Hash for gapped one
• use Hash instead of Array when you can't predict data size
• create Array with needed values when you can predict your
  contiguous data size

Using that rules, memoization (just in your case, where COINS.size << amount and both datas are contiguous) might look like:

COINS = [25, 10, 5, 1]

def count_ways(amount)
  # memo is just COINS.size + 1 Array instances
  # a[0] = 1 instead of return 1 if amount == 0
  memo = Array.new(COINS.size){ Array.new(amount).tap{ |a| a[0] = 1 } }
  num_ways(amount, 0, memo)
end

def num_ways(amount, index, memo)
  return 0 if index >= COINS.size || amount < 0

  memo[index][amount] ||=
    num_ways(amount - COINS[index], index, memo) +
    num_ways(amount, index + 1, memo)
end

P.S. dynamic-programming tag is unnecessary :)