1. 动态规划解股票买卖问题从入门到精通股票买卖问题是算法学习中经典的动态规划应用场景。这类问题看似简单却蕴含着丰富的状态转移思想。今天我们就来深入剖析三道LeetCode上的股票买卖问题121、122、123题掌握如何用动态规划解决不同约束条件下的最优交易策略。1.1 问题背景与核心思路股票买卖问题的核心是在给定的价格序列中通过买卖操作获取最大利润。不同的问题变体会对交易次数、持股状态等做出限制。动态规划之所以适合这类问题是因为具有最优子结构最终最大利润取决于子问题的解存在重叠子问题不同天的状态会重复计算需要记录状态持股与否会影响后续决策我们将使用状态机的方法来建模定义dp[i][j]表示第i天处于j状态时的最大利润。关键在于准确定义状态含义正确写出状态转移方程合理初始化边界条件2. 单次交易问题121题2.1 问题描述与建模给定一个数组prices其中prices[i]是某股票第i天的价格。你只能完成一次买卖买入和卖出一支股票求最大利润。状态定义dp[i][0]第i天不持有股票时的最大利润dp[i][1]第i天持有股票时的最大利润状态转移dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i-1]) dp[i][1] max(dp[i-1][1], -prices[i-1])注意prices数组是0-based索引而dp数组是1-based所以prices[i-1]对应第i天的价格2.2 关键实现细节class Solution: def maxProfit(self, prices: List[int]) - int: n len(prices) dp [[0]*2 for _ in range(n1)] dp[0][1] -float(inf) # 第0天持有股票不合法 for i in range(1, n1): dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i-1]) dp[i][1] max(dp[i-1][1], -prices[i-1]) return dp[n][0]注意事项初始化dp[0][1]为负无穷表示不可能的状态只能买卖一次所以买入时的利润是-prices[i-1]没有之前的利润积累最终结果是dp[n][0]因为卖出股票后才能实现利润2.3 复杂度分析时间复杂度O(n)只需遍历一次价格序列空间复杂度O(n)可以优化到O(1)只保存前一天的状态3. 多次交易问题122题3.1 问题变化与调整现在允许进行多次交易买入和卖出一支股票多次但不能同时参与多笔交易必须在再次购买前出售掉之前的股票。状态定义不变但状态转移变化dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i-1]) dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i-1])关键区别在于买入时的利润计算dp[i-1][0] - prices[i-1]这表示可以累积之前的利润。3.2 实现代码class Solution: def maxProfit(self, prices: List[int]) - int: n len(prices) dp [[0]*2 for _ in range(n1)] dp[0][1] -float(inf) for i in range(1, n1): dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i-1]) dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i-1]) return dp[n][0]3.3 实战技巧这题也可以用贪心法收集所有上升区间的利润动态规划的优势在于可以处理更复杂的约束条件空间优化版本hold, not_hold -float(inf), 0 for price in prices: hold max(hold, not_hold - price) not_hold max(not_hold, hold price) return not_hold4. 最多两次交易问题123题4.1 状态扩展与建模现在限制最多可以完成两笔交易。我们需要扩展状态来表示不同的交易阶段。五种状态无操作第一次买入第一次卖出第二次买入第二次卖出状态转移dp[i][0] dp[i-1][0] dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i-1]) dp[i][2] max(dp[i-1][2], dp[i-1][1] prices[i-1]) dp[i][3] max(dp[i-1][3], dp[i-1][2] - prices[i-1]) dp[i][4] max(dp[i-1][4], dp[i-1][3] prices[i-1])4.2 完整实现class Solution: def maxProfit(self, prices: List[int]) - int: n len(prices) dp [[0]*5 for _ in range(n1)] # 初始化非法状态 for j in range(1, 5): dp[0][j] -float(inf) for i in range(1, n1): dp[i][0] dp[i-1][0] dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i-1]) dp[i][2] max(dp[i-1][2], dp[i-1][1] prices[i-1]) dp[i][3] max(dp[i-1][3], dp[i-1][2] - prices[i-1]) dp[i][4] max(dp[i-1][4], dp[i-1][3] prices[i-1]) return max(dp[n][0], dp[n][2], dp[n][4])4.3 关键点解析状态1和3表示持有股票状态2和4表示不持有每次买入都依赖前一次卖出的利润最终结果取max(dp[n][0], dp[n][2], dp[n][4])因为可能在0次、1次或2次交易后获得最大利润5. 常见问题与调试技巧5.1 数组索引偏移问题股票价格数组通常是0-based第0天到第n-1天而dp数组为了处理边界条件常用1-based第0天到第n天。常见的错误包括错误地使用prices[i]而不是prices[i-1]忘记初始化dp[0][j]的边界条件调试技巧打印出完整的dp表格检查每个状态的转移是否符合预期5.2 状态转移错误常见错误包括混淆买入和卖出的状态转移方向在多次交易问题中忘记累积之前的利润在两次交易问题中错误地连接状态转移检查方法手动计算小例子如3天的价格序列验证dp值是否正确5.3 空间优化实现上述解法空间复杂度都是O(n)实际上可以优化到O(1)def maxProfit(prices): # 121题空间优化 min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit # 123题空间优化 buy1 buy2 -float(inf) sell1 sell2 0 for price in prices: buy1 max(buy1, -price) sell1 max(sell1, buy1 price) buy2 max(buy2, sell1 - price) sell2 max(sell2, buy2 price) return max(sell1, sell2, 0)6. 扩展与变种问题掌握了这三道基础问题后可以尝试以下变种含冷冻期卖出后需要等待一天才能买入含交易手续费每次卖出需要扣除手续费最多k次交易将两次交易推广到k次这些问题的解决思路都是类似的定义足够的状态正确写出状态转移方程处理好边界条件。在实际面试中建议先从简单版本开始逐步扩展到复杂情况。动态规划问题的解决关键在于明确状态定义正确推导状态转移合理初始化确定最终解的位置通过反复练习这些股票买卖问题可以深入理解动态规划的状态设计和转移技巧为解决更复杂的动态规划问题打下坚实基础。
