通过备忘录实现最低硬币兑换量？

Question

我正在练习动态规划的概念（递归不是我的强项）。我想知道如何改进我的代码，以避免堆栈溢出

任何有帮助的，谢谢

def coinFlipping(n):
    """
    For n amount of change, return the minimal amount of currency in coins.

    Top-Down Approach (Memoization): Memo dictionary stores already solved
    subproblems to reuse and avoid recomputing. It's essentially recursion 
    but optimized to avoid recomputing results. 
    """
    COINS = {
        "penny": 0.01,
        "nickel": 0.05,
        "dime": 0.10,
        "quarter": 0.25,
        "dollar": 1.00
    }

    memo = {}

    def __coinFlipping(n):

        if n not in memo:
            # Base case (if n is equal to 0.01, 0.05, 0.10, 0.25..)
            if n in COINS.values():
                memo[n] = 1
            else:
                results = []
                coins = (coin for coin in COINS.values() if coin < n)
                for coin in coins:
                    results.append(__coinFlipping(n - coin))
                memo[n] = 1 + min(results)
        else:
            return memo[n]         
    __coinFlipping(n)
    print(memo[n])

coinFlipping(10)

我得到了以下错误：

File "/mnt/d/programs/algorithms/dynamicProgramming.py", line 45, in __coinFlipping
    results.append(__coinFlipping(n - coin))
  File "/mnt/d/programs/algorithms/dynamicProgramming.py", line 45, in __coinFlipping
    results.append(__coinFlipping(n - coin))
  File "/mnt/d/programs/algorithms/dynamicProgramming.py", line 45, in __coinFlipping
    results.append(__coinFlipping(n - coin))
  [Previous line repeated 993 more times]
  File "/mnt/d/programs/algorithms/dynamicProgramming.py", line 44, in __coinFlipping
    for coin in coins:
  File "/mnt/d/programs/algorithms/dynamicProgramming.py", line 43, in <genexpr>
    coins = (coin for coin in COINS.values() if coin < n)
RecursionError: maximum recursion depth exceeded in comparison

Answer 1

user2864740恰到好处。更改为整数，代码将运行

Answer 2

谢谢@user2864740 和@dannyadam

我将把我的最终代码留给以后看这篇文章的人

def coinFlipping(n):
    """
    For n amount of cents, return the minimal amount of currency in coins.

    Top-Down Approach (Memoization): Memo dictionary stores already solved
    subproblems to reuse and avoid recomputing. It's essentially recursion 
    but optimized to avoid recomputing results. 
    """
    COINS = {
        "dollar": 100,
        "quarter": 25,
        "dime": 10,
        "nickel": 5,
        "penny": 1
    }

    memo = {}

    def __coinFlipping(change):

        if change not in memo:
            # Base case (if n is equal to 0.01, 0.05, 0.10, 0.25..)
            if change in COINS.values():
                memo[change] = 1
            else:
                results = []
                coins = [coin for coin in COINS.values() if coin < change]
                for coin in coins:
                    results.append(__coinFlipping(change - coin))
                memo[change] = 1 + min(results)
        return memo[change]         
            
    __coinFlipping(n)
    print(memo[n])

coinFlipping(42)

在实现了这个示例之后，我开始认为这是一个糟糕的记忆玩具示例。我可以编写一个贪婪算法，在每一步选择价值最大的硬币。e、 g.从42c中减去25c，从17c中减去10c，以此类推，同时递增计数器