python - python中的记忆硬币变化（递归解决方案）

Question

我对python相当陌生，我正在练习我在网上找到的几个问题（这个是eulerproject q31）。我想出了2种方法来解决它。问题：找出使用特定硬币组（例如美元 {1,5,10,25}）为给定金额找零的所有方法

这是我的递归解决方案的代码

def count(s, m, n):
    if (n < 0):
        return 0;
    if (m <=0 and n >= 1):
        return 0
    if (n == 0):
        return 1
    return count( s, m - 1, n) + count(s, m, n-s[m-1] ); 

S 是硬币组 {1,5,10,25} m 是硬币组的长度（在本例中为 4），n 是输入数量

这工作得很好，除了当我尝试给它一个更大的值，比如 7000 时，我在网上查了一下，似乎我的解决方案将包括多次包含先前递归迭代的子问题（使其达到最大递归限制） . 我试图弄清楚如何使用我可以使用 Java 但不知道如何在 python 中处理的 memoization 来做到这一点。任何人都可以就我应该如何记忆这个算法提供任何指导，以便它跳过检查已经检查过的子问题吗？谢谢！

标签： pythonrecursionoptimizationmemoization

Answer 1

存储您计算的金额。

def make_change(coins, n):
    dic_ways = {}

    def helper(index, n):
        if n == 0:
            return 1
        if n < 0:
            return 0
        num_ways = 0
        for i in range(index, len(coins)):
            coin = coins[i]
            if n - coin not in dic_ways:
                num_ways += helper(i + 1, n - coin)
                dic_ways[n-coin] = True
        return num_ways

    return helper(0, n)

如您所见，n 是数量。当您遇到已计算的金额时，您只需跳过它。