用函数递归的方法实现迭代求解

Question

我正在尝试解决leetcode上的以下问题：硬币兑换2

输入：金额=5，硬币=[1,2,5]输出：4说明：有四种方法来弥补金额：

5=5

5=2 2 1

5=2 1 1 1

5=1 1 1 1 1

我试图实现一个迭代的解决方案，本质上模拟/模仿递归使用堆栈。我已经设法实现了它，解决方案有效，但它超过了时间限制。

我注意到递归解决方案利用记忆进行优化。我也想在我的迭代解决方案中包含这一点，但我不知道如何继续。

到目前为止，我的解决方案是：

# 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

我已经尝试使用字典记录附加到堆栈如下：

#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'

例如，如果进行了sum=2和coin数组index=1的调用（2,1），我将其附加到字典中。如果再次遇到相同的调用，我不会再次追加它。但是，它不起作用，因为不同的组合可以有相同的总和和索引。

不管怎样，我可以在上面的迭代解决方案中加入记忆化。我想这样做，使它在功能上与递归解决方案相同。

Answer 1

我设法找到了解决办法。本质上，我使用了后序遍历，并使用状态变量来记录当前调用所处的递归阶段。在舞台上，我在自上而下之后，成功地做到了自下而上。

我提出的解决方案如下：

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