Implementing iterative solution in a functionally recursive way with memoization

Question

I am trying to solve the following problem on leetcode: Coin Change 2

Input: amount = 5, coins = [1, 2,5] Output: 4 Explanation: there are four ways to make up the amount:

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

I am trying to implement an iterative solution which essentially simulates/mimic recursion using stack. I have managed to implement it and the solution works, but it exceeds time limit.

I have noticed that the recursive solutions make use of memoization to optimize. I would like to incorporate that in my iterative solution as well, but I am lost on how to proceed.

My solution so far:

# stack to simulate recursion
stack = []
# add starting indexes and sum to stack
#Tuple(x,y) where x is sum, y is index of the coins array input
for i in range(0, len(coins)):
    if coins[i]<=amount:
        stack.append((coins[i], i))

result = 0
while len(stack)!=0:
    c = stack.pop()
    currentsum = c[0]
    currentindex = c[1]
    # can't explore further
    if currentsum >amount:
        continue
    # condition met, increment result
    if currentsum == amount:
        result = result+1
        continue
    # add coin at current index to sum if doesn't exceed amount (append call to stack)
    if (currentsum+coins[currentindex])<=amount:
        stack.append((currentsum+coins[currentindex], currentindex))
    #skip coin at current index (append call to stack)
    if (currentindex+1)<=len(coins)-1:
        stack.append((currentsum, currentindex+1))

return result

I have tried using dictionary to record appends to the stack as follows:

#if the call has not already happened, add to dictionary
if dictionary.get((currentsum, currentindex+1), None) == None:
   stack.append((currentsum, currentindex+1))
   dictionary[currentsum, currentindex+1)] = 'visited'

Example, if call (2,1) of sum = 2 and coin-array-index = 1 is made, I append it to dictionary. If the same call is encountered again, I don't append it again. However, it does not work as different combinations can have same sum and index.

Is there anyway I can incorporate memoization in my iterative solution above. I want to do it in a way such that it is functionally same as the recursive solution.

user_13701706 · Answer

I have managed to figure out the solution. Essentially, I used post order traversal and used a state variable to record the stage of recursion the current call is in. Using the stage, I have managed to go bottom up after going top down.

The solution I came up with is as follows:

def change(self, amount: int, coins: List[int]) -> int:
    if amount<=0:
        return 1
    if len(coins) == 0:
        return 0  
    d= dict()
    #currentsum, index, instruction
    coins.sort(reverse=True)
    stack = [(0, 0, 'ENTER')]
    calls = 0
    while len(stack)!=0:
        currentsum, index, instruction = stack.pop()
        if currentsum == amount:
            d[(currentsum, index)] = 1
            continue
        elif instruction == 'ENTER':
            stack.append((currentsum, index, 'EXIT'))
            
            if (index+1)<=(len(coins)-1):
                if d.get((currentsum, index+1), None) == None:
                    stack.append((currentsum, index+1, 'ENTER'))
            
            newsum = currentsum + coins[index]
            if newsum<=amount:
                if d.get((newsum, index), None) == None:
                    stack.append((newsum, index, 'ENTER'))
        elif instruction == 'EXIT':
            newsum = currentsum + coins[index]
            left = 0 if d.get((newsum, index), None) == None else d.get((newsum, index))
            right = 0 if d.get((currentsum, index+1), None) == None else d.get((currentsum, index+1))
            d[(currentsum, index)] = left+right
        calls = calls+1
    print(calls)
    return d[(0,0)]

Implementing iterative solution in a functionally recursive way with memoization

1 Answers