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

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恰到好处。更改为整数，代码将运行