educative.io

Why doesn't my memoization code work?

Courses
,
#1

Why does my code time out even with stress testing set to False?

memo={}

memo[0]=1

def ways(bills,amount):

if (bills==[]):

if amount ==0:

  memo[(tuple(bills),amount)]=1

  return 1

else:

  memo[(tuple(bills),amount)]=0

  return 0

bills.sort()

if amount==0:

memo[(tuple(bills),amount)]=1

return 1

elif amount < min(bills):

memo[(tuple(bills),amount)]=0

return 0

if (tuple(bills),amount) in memo:

return memo[(tuple(bills), amount)]

else:

l= amount // bills[0]

s=0

for i in range(l):

  s=s+ways(bills[1:],amount -(i+1)*bills[0] )

memo[(tuple(bills), amount -(i+1)*bills[0])]=s

return s

def countways(bills, amount):

write your code here

return ways(bills,amount)

stressTesting = False

I’m using memoization so whats the problem?

#2

Hi @Hao_Sun,
Your solution code is correct, but it is inefficient for a larger set of bills, despite the implementation of memoization. The last test case in the challenge ([1-39], 190) is where your code would get stuck and time out.
The problem lies with placing the recursive function call inside the for loop. Without memoization, the time complexity for which could be O(n!) or O(2^n). You can reduce it significantly with memoization but only if you use it correctly. Your inefficiency problem is in the following segment of code:

    else:
        l = amount // bills[0]
        s = 0
        for i in range(l):
            s = s+ways(bills[1:], amount - (i+1)*bills[0])
        memo[(tuple(bills), amount - (i+1)*bills[0])] = s
        return s

If we dry run your code, the value of l in the first function call would be 190 (190//1), which means that the first function will make 190 recursive calls, and those 190 will, in turn, make 85 recursive calls (190//2), and so on. As you can see, there are many calls, and memoization won’t be of much help in this case as the recursion tree is too large.
I recommend you tweak your solution logic for the for loop a little such that the max number of steps in your loop doesn’t exceed the total number of bills available. You can also check out the memoization-based recursion solution for this challenge on the platform for any further hints.

#3

But there is no way to avoid large recursion trees as this problem is NP-hard.

It’s been a while, but I think the essence of the recursion here is that you decide how much of
bill i to use unless you already know. So you need to compute the subproblems number ways to make change using 1 of bill i 2 of bill i 3 of bill i … for some bill i. as thats the only way we can recurse.
Also not all the subproblems call 85 recursive calls subproblem i only makes (190-i)/2 recursive calls.

#4

Yeah, you’re right; some subproblems will have much fewer recursive calls than 85. My bad on that part. You’re also right that the recursion tree will always be large. But, even though it is an NP-hard problem, our solution logic can still influence the recursion tree. We cannot make it smaller, but it can become larger depending on our solution logic.

I also happened to modify your code and the similar solution code on educative to test out the final test case and compare both solutions. I found out that for bills [1-39] and amount 190, educative’s solution makes ~79,000 recursive calls, while your given solution here makes 820,000 calls for an amount of 80 (takes too long for 190). Surprisingly, in neither code, any memoized combination ever repeats itself, as the following if condition is never satisfied:

  if (amount, maximum) in memo: # checking if memoized
    return memo[(amount, maximum)]

Meaning memoization plays no part in the final test case in either solution. Besides, I think the best solution to a coin change problem (which this challenge essentially was) should be the bottom-up dynamic programming approach without recursion. Like every problem, this problem requires a programming approach that best solves it. In this case, it wasn’t best solved by recursion.