动态规划解决方案不适用于变更问题？

Question

我很好奇为什么我解决变革问题的方法没有成功。这个逻辑对我来说很有意义，所以我不确定失败在哪里。

def count_change(denoms, denoms_length, amount):
    """
    Finds the number of ways that the given number of cents can be represented.
    :param denoms: Values of the coins available
    :param denoms_length: Number of denoms
    :param amount: Given cent
    :return: The number of ways that the given number of cents can be represented.
    """

    # Write your code here!
    return helper(denoms, amount)

def helper(denoms, amount, i=0):
    if amount == 0:
        return 1
    elif i >= len(denoms):
        return 0
    else:
        count = 0
        coin = denoms[i]
        if coin < amount:
            mult = amount // coin
            for m in range(1, mult+1):
                count += helper(denoms, amount - (coin*m), i+1)
        else:
            count += helper(denoms, amount, i+1)
        
        return count

count_change([25, 10, 5, 1], 4, 30)
>>> 1 #should be 18

这个问题是付费墙后面的，所以我无法链接。最让我困惑的部分是当一枚硬币有几个小于金额的倍数时。这就是 else 子句中 for 循环背后的精神。

我在这里做错了什么？

Answer 1

def count_change(denoms, denoms_length, amount):
    return helper(denoms, amount)

def helper(denoms, amount, i=0):
    if amount == 0:
        return 1
    elif i >= len(denoms):
        return 0
    else:
        count = 0
        coin = denoms[i]

        mult = amount // coin
        for m in range(0, mult+1):
            count += helper(denoms, amount - (coin*m), i+1)
        
        return count

count_change([25, 10, 5, 1], 4, 30)

我们改变了一些事情。 我们应该问自己代码应该如何工作。 它递归地处理每个硬币，决定我们要在答案中使用多少个硬币。

我们可以使用从 0 到最大的任意数量（你称之为

mult

）。
请注意，如果硬币精确等于

amount

，原始代码将不会使用硬币，因为

if coin < amount:

。我们现在可以将其更改为

if coin <= amount:

。

接下来，你应该注意到我们不会尝试使用0币。这种情况仅由嵌套的

else

管辖。这是错误的——不使用硬币是一个可行的选择！所以我们应该把

else

子句中的第二部分去掉。现在我们可以意识到，以 0 为起点扩展 for 循环可以完成同样的事情。现在代码可以运行了。

现在，我们应该讨论一下动态规划的思想。该解决方案使用与动态编程相同的思想，但它是递归的。每个计数的表示都来自

return 1

。这会导致大量的计算。 为了解决这个问题并使其成为最简单的动态编程解决方案，我们可以使用一种称为记忆化的技术。

def count_change(denoms, denoms_length, amount):
    memory = {}

    def helper(amount, i=0):
        if amount == 0:
            return 1

        if i >= len(denoms):
            return 0

        if (amount, i) not in memory:
            count = 0
            coin = denoms[i]

            mult = amount // coin
            for m in range(0, mult+1):
                count += helper(amount - (coin*m), i+1)

            memory[(amount, i)] = count

        return memory[(amount, i)]

    return helper(amount)

我们添加了一个字典

memory

，确保每对

(amount, i)

只处理一次，从而降低时间复杂度。此外，从辅助参数中删除了分项，因为它在整个过程中保持不变。

更经典的动态编程方法会使用

amount x denoms_length

大小的数组，并用所有选项的答案填充它。如果你小心翼翼地做到这一点，你甚至可以将复杂性降低到一个很酷的

O(amount * denoms_length)

，但那是另一天的故事了。

Answer 2

只是忍不住尝试这个真正的DP解决方案来演示如何更容易地翻译以前的memo版本到DP版本（甚至上一篇文章已经很好地解释了所有逻辑.. .)

它使用一维ways来存储所有可能的结果，并最终返回最后一个。

def count_changes(coins: List[int], amt: int) -> int:
    coins.sort()          # ascending order to ease later processing 
    ways = [1] + [0] * amt

    # Time: O(amt * coins)
    for coin in coins:
        for x in range(coin, amt + 1):
            ways[x] += ways[x - coin]
            #print(ways)
            
    return ways[amt]

if __name__ == '__main__':
    coins = [1, 5, 10, 25]

    print(count_changes(coins, 22))    #  9
    print(count_changes(coins, 30))    # 18