如何计算表示n分的方式数

Question

我正在研究以下算法，想知道我的实现是否正确：

给定无限数量的四分之一、一角硬币、五分硬币和便士，编写代码来计算表示 n 美分的方法数

这是没有记忆的：

def count_ways(n)
  return 0 if n < 0 
  return 1 if n == 0 

  count_ways(n-25) + count_ways(n-5) + count_ways(n-10) + count_ways(n-1)
end

Answer 1

不，您将重复计算解决方案，因为您可以先选择四分之一，然后选择一角硬币或其他方式，但这些解决方案本质上是相同的。

防止重复计算的最简单方法是确保您永远不会选择比您已经选择的硬币大的硬币。

在代码中：

def count_ways(n, max_coin)
  return 0 if n < 0 
  return 1 if n == 0 

  result = count_ways(n-1, 1)
  result = result + count_ways(n- 5,  5) if max_coin >=  5
  result = result + count_ways(n-10, 10) if max_coin >= 10
  result = result + count_ways(n-25, 25) if max_coin >= 25
  result
end

并用 25 作为初始最大硬币调用它