动态规划：在 ProjectEuler 上的问题 31 上将自下而上的方法转换为自上而下的方法

Question

为了学习，我想用top-down DP解决Project Euler上的[problem 31] (https://projecteuler.net/problem=31)。我已经用蛮力和自下而上的动态规划解决了它。

问题总结：总和为 2 英镑的独特组合的数量（顺序无关紧要），硬币为 1p、2p、5p、10p、20p、50p、1 英镑、2 英镑。

我已经尝试了几次，但我的结果确实考虑到了顺序。我试图通过包含一个“upperLimit”变量来排除这一点，它的工作是永远不会包含一个更有价值的硬币（消除像 5,1,2,1 这样的可能性，而不是 5,2,1,1）

但是，它仍然没有产生正确的结果。这是我的代码，在 TOP DOWN 下面我包含了有效的自下而上方法。

让我们简化为 5 便士而不是 200 便士，硬币为 1、2、5。这应该产生 4 种组合：5、221、2111、11111。

我的代码自上而下输出 5 个组合，而自下而上正确输出 4 个。

自上而下的方法（还没有用）

combos = [0 for x in range(0,201)]


def combinations(currentValue, upperLimit = 200):
    #Reset counter
    numbOfCombos = 0

    #If we reach leaf
    if currentValue == 0:
        return 1    

    #If the value is already known, return it
    elif combos[currentValue] != 0:
        return combos[currentValue]

    #Else recurse through the tree
    else:
        if currentValue >= 200:
            numbOfCombos = numbOfCombos + combinations(currentValue-200, 200)
        if currentValue >= 100 and upperLimit >= 100:
            numbOfCombos = numbOfCombos + combinations(currentValue-100, 100)
        if currentValue >= 50 and upperLimit >= 50:
            numbOfCombos = numbOfCombos + combinations(currentValue-50, 50)
        if currentValue >= 20 and upperLimit >= 20:
            numbOfCombos = numbOfCombos + combinations(currentValue-20, 20)
        if currentValue >= 10 and upperLimit >= 10:
            numbOfCombos = numbOfCombos + combinations(currentValue-10, 10)
        if currentValue >= 5 and upperLimit >= 5:
            numbOfCombos = numbOfCombos + combinations(currentValue-5, 5)
        if currentValue >= 2 and upperLimit >= 2:
            numbOfCombos = numbOfCombos + combinations(currentValue-2, 2)
        if currentValue >= 1 and upperLimit >= 1:
            numbOfCombos = numbOfCombos + combinations(currentValue-1, 1)

        combos[currentValue] = numbOfCombos
        return combos[currentValue]

print(combinations(5,))

自下而上的方法（有效）

targetValue = 200;

coins = [1, 2, 5, 10, 20, 50, 100, 200];
combinations = [0 for x in range(0,targetValue+1)];
combinations[0] = 1;

for i in range(0, len(coins)):
    for j in range(coins[i], targetValue+1):
        combinations[j] = combinations[j] + combinations[j - coins[i]];

print(combinations);

Output

非常感谢任何tips/advice或完整的解决方案。我知道自下而上的解决方案可能是最有效和最漂亮的，但为了学习思维过程，我想使用 TOP-DOWN 解决它。

谢谢！

Answer 1

它正在数 1,1,2,1 因为当它在数带有 2,* 的解决方案时，它记住 3p 的 2 个解决方案，然后计算 1,1,*.

的 2 个解决方案

解决方法是在记忆中包含 upperLimit。（我还添加了一个缺少测试 upperLimit >= 200。）见下文。

combos = {}


def combinations(currentValue, upperLimit=200):
    # Reset counter
    numbOfCombos = 0

    # If we reach leaf
    if currentValue == 0:
        return 1

    # If the value is already known, return it
    elif (currentValue, upperLimit) in combos:
        return combos[currentValue, upperLimit]

    # Else recurse through the tree
    else:
        if currentValue >= 200 and upperLimit >= 200:
            numbOfCombos = numbOfCombos + combinations(currentValue - 200, 200)
        if currentValue >= 100 and upperLimit >= 100:
            numbOfCombos = numbOfCombos + combinations(currentValue - 100, 100)
        if currentValue >= 50 and upperLimit >= 50:
            numbOfCombos = numbOfCombos + combinations(currentValue - 50, 50)
        if currentValue >= 20 and upperLimit >= 20:
            numbOfCombos = numbOfCombos + combinations(currentValue - 20, 20)
        if currentValue >= 10 and upperLimit >= 10:
            numbOfCombos = numbOfCombos + combinations(currentValue - 10, 10)
        if currentValue >= 5 and upperLimit >= 5:
            numbOfCombos = numbOfCombos + combinations(currentValue - 5, 5)
        if currentValue >= 2 and upperLimit >= 2:
            numbOfCombos = numbOfCombos + combinations(currentValue - 2, 2)
        if currentValue >= 1 and upperLimit >= 1:
            numbOfCombos = numbOfCombos + combinations(currentValue - 1, 1)

        combos[currentValue, upperLimit] = numbOfCombos
        return numbOfCombos


print(combinations(5))

Answer 2

可以使用 Coin Change | DP-7

简化发布自上而下的方法（即更少的条件）并推广到任何一组硬币

对于一组硬币 S，我们将解决方案 space 分成两组：

不包含第 m 个硬币（或 S[m）的解决方案。
至少包含一个 S[m] 的解。令 count(S, m, target) 为计算解数的函数，则可写为 count(S, m-1, target) 与 count(S, m, target-S[米]).

代码

def count(S, target):
    '''
        Returns the count of ways we can sum
        S[0...m-1] coins to get sum target
    
    '''
    def recur(m, target):
        # Helper function to enable Memoization 
        # If target is 0 then there is 1
        # solution (do not include any coin)
        if (target == 0):
            return 1

        # target < 0 -> no solution exists
        if (target < 0):
            return 0
   
        # no coins and target > 0 -> no solution
        if (m <=0 and target > 0):
            return 0
         
        # Check if coin combination and target amount have been solved before
        if (m, target) in lookup:
            return lookup[(m, target)]

        # sum of two solutions:
        # 1.  does not use m coin i.e.            recur (m-1, target)
        # 2.  uses at least one of m-th coin i.e. recur(m, target - S[m-1])
        # including S[m-1] (ii) excluding S[m-1]
        lookup[(m, target)] = recur(m - 1, target ) + recur(m, target - S[m-1])
        
        return lookup[(m, target)]
    
    lookup = {}
    
    return recur(len(S), target)

测试

arr = [1, 2, 5, 10, 20, 50, 100, 200]
print(count(arr, 200))
# Output: 73682

动态规划：在 ProjectEuler 上的问题 31 上将自下而上的方法转换为自上而下的方法

Dynamic Programming: Convert bottom-up approach to top-down on Problem 31 on ProjectEuler

python

algorithm

dynamic-programming