递归记忆方法邮票问题

Question

上下文： 我们提供各种面额的邮票，如 1、5、66、85、100。 假设我们有无限数量的每种面额的邮票，并且我们希望使用尽可能少的邮票数量达到某个值，例如 138。 一方面，我们可以有

138 = 100+5+5+5+5+5+5+5+1+1+1 （11 个邮票），

但最好使用

138 = 66+66+5+1 （ 4枚邮票）。

问题是创建一个函数 min_stamps(x,den) 来返回金额 x 所需的最小邮票数量，其中 den是可用邮票面额的元组。我们假设所有金额都是正整数，并且 den 包含 1，这保证了每个金额都是可能的。

我们被要求对这个问题使用递归记忆方法。我的尝试如下。

def min_stamps(x,den):
    global MEMO
    if (x,den) not in MEMO:
        exc = min_stamps(x, den[:-1])
        if den[-1] > x:
            MEMO[(x,den)] = exc
        else:
            inc = min_stamps(x-den[-1], den[:-1])
            MEMO[(x,den)] = min(inc,exc)
    return MEMO[(x,den)]

当在 min_stamps(138,(1,5,66,85,100)) 上使用上面的函数时，我得到 RecursionError: Maximum recursion Depletished。我希望从这个价值面额对中得到 4，但我不确定如何解决这个问题，并且我不确定上面代码中解决问题的逻辑是否完全正确。

Answer 1

首先，您的逻辑是错误的。

我的猜测是，您获得无限递归的原因是因为

exc = min_stamps(x, den[:-1])

您的代码永远不会通过此行。第一个执行，den =（1,5,66,85,100），之后den =（1,5,66,85），之后=（1,5,66,85） ....直到其空正确？但是，即使是空的，den [-1]仍然是（），因此是无限的递归。
另外，我认为您的整个代码完全是错误的，我认为我真的不理解。

其次，没有终止递归的基本案例。

这就是我写

def f(x, den) :
 global mem
 # memoization
 if x in mem: return mem[x]
 # base case, when the value is one of the stamps, there's exactly one way to make it
 elif x in den: return 1
 # prevents negative values from being counted
 elif x<0: return float("inf")
 # the main logic
 else:
  mem[x] = float("inf")
  for stamp on den:
   mem[x] = min(mem[x], f(x-stamp, den) +1) 
  return mem[x]

这件代码的方式，因为最小数量的方法将涉及从数字中的任何邮票的值进行亚键值。我们添加1个原因是使用一张邮票的价值。递归进行此操作并进行回忆，您有标准的动态编程问题