LeetCode 121买卖股票最佳时机：求DP记忆化实现帮助

问题描述 #

给定数组prices，其中prices[i]代表第i天的股票价格。需选择一天买入股票，再选择未来某一天卖出以最大化利润，若无法获利则返回0。

原代码问题分析 #

你的递归尝试存在几个核心问题，导致记忆化失效：

1. DP数组维度错误：dp = [["abc"]*2**n for _ in range(n)]中2^n的长度完全冗余，状态设计偏离问题本质
2. 赋值操作错误：dp[buy][index]==prices[index]-prices[buy]使用了比较运算符==而非赋值运算符=，无法存储计算结果
3. 记忆化逻辑混乱：递归中判断dp[index][index+1]和dp[buy][index+1]的条件不成立，且未正确复用已计算的状态
4. 状态覆盖不全：buy=-1时的递归分支处理模糊，未覆盖所有有效交易场景

修正后的记忆化DP实现（针对单次交易） #

针对本题只能进行一次买卖的限制，我们可以设计更简洁的记忆化递归方案，用缓存记录从某一天开始的最大利润，避免重复计算：

方案1：使用lru_cache自动记忆化 #

from functools import lru_cache
from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0
        
        @lru_cache(maxsize=None)
        def dfs(start):
            # 返回从第start天开始到结束的最大利润
            if start >= n - 1:
                return 0
            current_max = 0
            # 遍历所有可能的卖出日期
            for sell_day in range(start + 1, n):
                profit = prices[sell_day] - prices[start]
                if profit > 0:
                    # 取当前交易利润的最大值
                    current_max = max(current_max, profit)
                # 不选择在start天买入，直接计算sell_day开始的最大利润
                current_max = max(current_max, dfs(sell_day))
            return current_max
        
        return dfs(0)

方案2：手动维护DP数组实现记忆化 #

如果不想依赖lru_cache，可以手动维护一个DP数组存储已计算的状态：

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0
        
        # dp[start] 表示从第start天开始的最大利润，初始值-1表示未计算
        dp = [-1] * n
        
        def dfs(start):
            if start >= n - 1:
                return 0
            if dp[start] != -1:
                return dp[start]
            
            current_max = 0
            for sell_day in range(start + 1, n):
                profit = prices[sell_day] - prices[start]
                if profit > 0:
                    current_max = max(current_max, profit)
                current_max = max(current_max, dfs(sell_day))
            
            dp[start] = current_max
            return current_max
        
        return dfs(0)

更高效的DP状态转移（自底向上） #

如果追求更高效率，自底向上的DP方案可以避免递归开销，状态定义如下：

• dp[i][0]：第i天不持有股票的最大利润
• dp[i][1]：第i天持有股票的最大利润

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0
        
        # 初始化DP数组
        dp = [[0] * 2 for _ in range(n)]
        dp[0][1] = -prices[0]  # 第0天买入股票，利润为负的股价
        
        for i in range(1, n):
            # 不持有股票：要么之前就不持有，要么今天卖出
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            # 持有股票：要么之前就持有，要么今天买入（只能买一次，所以买入前利润为0）
            dp[i][1] = max(dp[i-1][1], -prices[i])
        
        return dp[-1][0]

这个方案的时间复杂度为O(n)，空间复杂度为O(n)，还可以进一步优化为O(1)空间，只维护前一天的状态：

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0
        
        prev_not_hold = 0
        prev_hold = -prices[0]
        
        for i in range(1, n):
            curr_not_hold = max(prev_not_hold, prev_hold + prices[i])
            curr_hold = max(prev_hold, -prices[i])
            
            prev_not_hold, prev_hold = curr_not_hold, curr_hold
        
        return prev_not_hold

内容的提问来源于stack exchange，提问作者Muhammad Umer Farooq