LeetCode买卖股票最佳时机II显式栈DFS记忆化实现报错排查

核心错误原因 #

• 状态计算逻辑完全错误。你的显式栈后序处理（EXIT阶段）的取值逻辑没有和递归版本对齐：递归版本中买入/卖出的收益需要在当前层加减当日股价，而你原代码直接取两个子状态的最大值，未做价格计算，无记忆化版本能跑通纯靠暴力穷举所有路径的总利润，属于巧合，本质是暴力DFS而非动态规划。
• 记忆化的基础前提不成立。递归版本的状态(i, buying)对应的最大收益是从第i天往后能获得的额外收益，和之前已经获得的利润完全无关，你栈元素中携带的profit参数完全冗余，不同路径访问同一状态时携带的profit不同，会导致缓存值逻辑混乱。
• 记忆化的状态定义不一致。你无记忆化版本的字典存储的是单条路径的总利润，而非状态的全局最大收益，本身就不符合记忆化动态规划的要求，加缓存逻辑后错误直接暴露。

修复后的正确代码 #

完全对齐递归版本的状态定义和逻辑，移除冗余的profit参数，在EXIT阶段统一计算状态值：

from typing import List
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 栈元素顺序：是否可买入、当前下标、操作指令
        stack = [(True, 0, 'ENTER')]
        dp_cache = dict()
        while stack:
            buying, index, ins = stack.pop()
            # 边界条件：遍历完所有天数后收益为0
            if index >= len(prices):
                dp_cache[(index, buying)] = 0
                continue
            if ins == 'ENTER':
                # 已缓存的状态直接跳过重复计算
                if (index, buying) in dp_cache:
                    continue
                # 压入EXIT指令，后序处理时计算当前状态值
                stack.append((buying, index, 'EXIT'))
                # 压入子节点：先压不操作分支，再压操作分支，保证后序处理顺序正确
                if (index + 1, buying) not in dp_cache:
                    stack.append((buying, index + 1, 'ENTER'))
                if (index + 1, not buying) not in dp_cache:
                    stack.append((not buying, index + 1, 'ENTER'))
            else:
                # 和递归逻辑完全对齐，计算当前状态的最大收益
                cooldown_profit = dp_cache[(index + 1, buying)]
                if buying:
                    op_profit = dp_cache[(index + 1, not buying)] - prices[index]
                else:
                    op_profit = dp_cache[(index + 1, not buying)] + prices[index]
                dp_cache[(index, buying)] = max(cooldown_profit, op_profit)
        return dp_cache[(0, True)]

内容的提问来源于stack exchange，提问作者Naharul Hayat