python - 动态规划问题的记忆。为什么以下解决方案不起作用？

Question

我在 Leetcode 上尝试以下问题：Best time to buy and sell stock II

基本上，我的方法是：

    [7,1,5,3,6,4]
      /        \
    Buy         Not Buy
 (profit=-7)     (profit=0)
 /       \ 
 Sell      Not Sell 
profit=-6     profit=-7

我正在尝试使用堆栈来探索状态空间的深度优先搜索方法。堆栈中的每个条目都是一个包含以下内容的元组：

• 当前利润
• 我们是否有能力购买
• 输入数组中的索引
• 指令是“ENTER”或“EXIT”。Enter 表示我们正在输入树中的节点。在向上的过程中，当我们从堆栈中弹出时，条目将是“退出”，这就是我们知道是时候获取最大子节点的时候了。

到目前为止，我已经实施了解决方案，并且它有效。

我没有记忆的解决方案如下，它通过了测试用例：

def maxProfit(self, prices: List[int]) -> int:

    # Stack tuple order -> profit, buying, index , stack_instruction
    stack = [(0, True, 0, 'ENTER')]
    d = dict()
    while stack:
        profit, buying, index, ins = stack.pop()
        if index >= len(prices):
            d[(index, buying)] = profit
            
        elif ins == 'ENTER':
            stack.append((profit, buying, index, 'EXIT'))
            
            if buying:  # Can buy
                stack.append((profit - prices[index], not buying, index+1,'ENTER'))
                    
            else: # Can sell
                stack.append((profit + prices[index], not buying, index+1, 'ENTER'))
                    
            # Skip / take no action
            stack.append((profit, buying, index+1, 'ENTER'))
        else:
            # on the way up post order traversal
            d[(index,  buying)] = max(d.get((index+1, not buying)), d.get((index+1,  buying)))
    print(d)
    return d.get((0, True))

基本上我一直在使用一个模拟递归的显式堆栈。递归等价物应如下所示：

    def maxProfit(self, prices: List[int]) -> int:
    dp = {}
    
    def dfs(i: int = 0, buying: bool = True) -> int:
        if i >= len(prices):
            return 0

        if (i, buying) in dp:
            return dp[(i, buying)]
        
        cooldown_profit = dfs(i + 1, buying)
        
        if buying:
            buying_profit = dfs(i + 1, not buying) - prices[i]
            dp[(i, buying)] = max(cooldown_profit, buying_profit)
         
        else:
            selling_profit = dfs(i + 1, not buying) + prices[i]
            dp[(i, buying)] = max(cooldown_profit, selling_profit)
        
        return dp[(i, buying)]
        
    return dfs()

但是，当我尝试使用以下代码添加（标记为 ** **）来实现 memoization 时，它无法给出正确的解决方案。有人可以指出我哪里出错了吗？

    def maxProfit(self, prices: List[int]) -> int:

    # Stack tuple order -> profit, buying, index , stack_instruction
    stack = [(0, True, 0, 'ENTER')]
    d = dict()
    while stack:
        profit, buying, index, ins = stack.pop()
        if index >= len(prices):
            d[(index, buying)] = profit
            
        elif ins == 'ENTER':
            stack.append((profit, buying, index, 'EXIT'))
            
            if buying:  # Can buy
                **if (index+1, not buying) not in d:**
                    stack.append((profit - prices[index], not buying, index+1,'ENTER'))
                    
            else: # Can sell
                **if (index+1, not buying) not in d:**
                    stack.append((profit + prices[index], not buying, index+1, 'ENTER'))
                    
            # Skip / take no action
            **if (index+1, buying) not in d:**
                stack.append((profit, buying, index+1, 'ENTER'))
        else:
            # on the way up post order traversal
            d[(index,  buying)] = max(d.get((index+1, not buying)), d.get((index+1,  buying)))
            
            
    print(d)
    return d.get((0, True))

标签： pythonalgorithmdynamic-programmingdepth-first-searchmemoization

Answer 1

我设法让记忆在我的代码中工作。因此，我正在回答我自己的问题。本质上，我的基本情况是错误的。

class Solution:
def maxProfit(self, prices) -> int:
    # index, buying, ins
    stack = [(0, True, 1)]
    d = dict()
    #calls = 0
    while stack:
        index, buying, ins = stack.pop()
        #calls +=1
        if index >= len(prices):
            d[(index, buying)] = 0
        elif ins == 1:
            stack.append((index, buying,  0))
            if (index + 1, not buying) not in d:
                stack.append((index + 1, not buying,1))
            if (index + 1,buying) not in d:
                stack.append((index + 1,  buying,1))
        else:
            lst = []
            if buying:
                lst.append(d.get((index+1, not buying)) - prices[index])
            else:
                lst.append(d.get((index+1, not buying)) + prices[index])
            
            lst.append(d.get((index+1, buying)))
            
            d[(index, buying)] = max(lst)
            
    #print(d)
    #print(calls)
    return d.get((0, True))