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

For the sake of learning, I want to solve [problem 31] (https://projecteuler.net/problem=31) on Project Euler using top-down DP. I have already solved it using both brute force and bottom-up Dynamic Programming.

Problem summary:
Number of unique combinations (order doesn’t matter) in which sums to £2, having the coins 1p, 2p, 5p, 10p, 20p, 50p, £1, £2.

I have done several attempts, but my result does take order into account. I tried to exclude this by including an "upperLimit" variable, whose job is to never include a more valuable coin (eliminating possibilities like 5,1,2,1, instead of 5,2,1,1)

However, it still doesn’t yield correct results. This is my code, and below the TOP DOWN I’ve included the bottom-up approach which works.

Lets simplify for 5p instead of 200p, with the coins 1,2,5. This should yield 4 combinations: 5, 221, 2111, 11111.

My code with top-down outputs 5 combinations, while the bottom up correctly outputs 4.

TOP-DOWN APPROACH (doesn’t work yet)

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,))

BOTTOM-UP APPROACH (works)

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

Any tips/advice or complete solutions are greatly appreciated. I know that the bottom-up solution is probably the most efficient and most beautiful, but for the sake of learning thought processes I’d like to solve it using TOP-DOWN.

Thanks!

>Solution :

It’s counting 1,1,2,1 because when it’s counting solutions with 2,*, it
memoizes 2 solutions for 3p, then counts 2 solutions for 1,1,*.

The fix is to include upperLimit in the memoization. (I also added a
missing test upperLimit >= 200.) See below.

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))