ruby - 内存两个数字组合的有效方法

Question

我正在研究一种算法，在给定无限数量的便士、10 美分、55 美分和 25 美分的情况下，计算构建 100 美分的方法的数量。

我最终得到了上面的结果(AFAIK 有效):

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

现在，我想记住这个算法。我发现考虑内存的一种有效方法是考虑我们将哪些输入重复传递给此函数。在这种情况下，我想记住数量和索引参数的组合。

通常，当我有两个参数时，我会构建一个二维数组作为内存的一种方式，但在这里意义不大。因此，您如何记住这两个参数？做这样的事情有意义吗？

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

我相信在解决算法任务时没有实现记忆化的通用方法。因为速度。您必须选择的方式取决于您的算法、输入数据等。一些必要的规则:

• 避免创建许多数据结构实例:h = {}; h[ [1,2] ]
= 3 将产生 COINS.size * amount Arrays just for keys
• 对连续数据使用Array，对gapped数据使用Hash
• 当您无法预测数据大小时，请使用Hash 而不是Array
• 在您可以预测您的
  时，使用所需的值创建数组连续数据大小

使用该规则，内存(就您的情况而言，COINS.size <<amount 和两个数据连续)可能看起来喜欢:

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

附言dynamic-programming 标签是不必要的:)