1. 问题背景与核心挑战这道题目在LeetCode股票买卖系列中属于难度分水岭它要求我们在最多完成两笔交易的前提下实现利润最大化。与基础版本只允许一次交易和无限交易版本相比两笔交易的限制使得状态管理复杂度呈指数级增长。我最初看到这个问题时直觉上认为只需要记录第一次买卖和第二次买卖两个状态就够了。但实际编写代码时发现这样的设计无法处理重叠交易时段的情况。比如当第一次卖出和第二次买入发生在同一天时这种状态转换就会变得非常棘手。2. 三维DP的状态定义艺术2.1 状态维度的精确定义正确的状态设计应该包含三个维度天数索引i处理到第几天交易次数k已完成多少次完整交易买入卖出持仓状态0/1当前是否持有股票用dp[i][k][0/1]表示第i天、已完成k次交易、当前持仓状态下的最大利润。这个三维结构完美覆盖了所有可能的情况。关键理解这里的k指已经完成的交易次数而不是正在进行的交易。这是很多初学者容易混淆的点。2.2 状态转移方程推导基于上述定义我们可以建立完整的状态转移关系dp[i][k][0]未持仓可能来自前一天也未持仓dp[i-1][k][0]或者前一天持仓今天卖出dp[i-1][k][1] prices[i]取两者最大值dp[i][k][1]持仓中可能来自前一天已持仓dp[i-1][k][1]或者前一天未持仓今天买入注意k的变化当k 0时dp[i-1][k-1][0] - prices[i]取两者最大值特别注意买入时的k-1操作这表示完成一次完整交易后k才增加。3. 边界条件与初始化技巧3.1 初始状态的设置dp[0][0][0] 0 第0天未持仓利润为0dp[0][0][1] -prices[0] 第0天买入利润为负股价dp[0][1][0] -inf 不可能在第0天已完成1次交易dp[0][1][1] -inf 同上dp[0][2][0] -inf 不可能在第0天已完成2次交易dp[0][2][1] -inf 同上3.2 空间优化策略虽然三维DP直观但实际编码时可以优化为二维数组。因为第i天的状态只依赖于第i-1天所以可以压缩掉天数维度dp [[[0]*2 for _ in range(3)] for _ in range(2)] # 使用模2循环利用空间 for i in range(1, n): for k in range(1, 3): dp[i%2][k][0] max(dp[(i-1)%2][k][0], dp[(i-1)%2][k][1] prices[i]) dp[i%2][k][1] max(dp[(i-1)%2][k][1], dp[(i-1)%2][k-1][0] - prices[i])4. 完整代码实现与逐行解析4.1 Python实现版本def maxProfit(prices): if not prices: return 0 n len(prices) dp [[[0]*2 for _ in range(3)] for _ in range(n)] # 初始化第一天状态 for k in range(3): dp[0][k][0] 0 dp[0][k][1] -prices[0] for i in range(1, n): for k in range(1, 3): # 未持仓状态 dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i]) # 持仓状态 dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) return dp[n-1][2][0]4.2 关键代码解析三维数组初始化dp[i][k][0/1]结构确保覆盖所有状态组合初始资金设为0初始持仓成本为-prices[0]双重循环逻辑外层遍历所有交易日内层遍历可能的交易次数1和2次状态转移实现未持仓状态考虑保持空仓或卖出获利持仓状态考虑保持持仓或新建仓位5. 常见错误与调试技巧5.1 典型错误模式交易次数计算错误错误做法在买入时增加k值正确做法只有在完成完整交易卖出后才增加k状态转移遗漏忘记考虑保持现状的转移路径只考虑改变状态的情况边界条件缺失未处理空输入情况未正确初始化第0天的所有可能状态5.2 调试检查清单当你的DP解法不通过时可以按照以下步骤排查打印DP表的前几行确认状态转移是否符合预期检查k的增减是否发生在正确的操作后验证初始状态是否覆盖所有可能性用简单测试案例如[1,2,3,4,5]手动推算DP表6. 算法复杂度与优化对比6.1 时间与空间分析时间复杂度O(n*k) → O(n)因为k最大为2空间复杂度原始三维DPO(nk2)优化后O(k*2) → O(1)常数空间6.2 替代解法对比峰谷法找出所有利润递增区间取最大的两个问题无法处理重叠交易时段适用场景交易次数无限制时状态机DP定义5个状态未操作、第一次买入、第一次卖出...本质上是对三维DP的另一种表述优点代码更简洁贪心算法尝试记录最小价格和最大利润无法正确处理两笔交易的情况7. 实战应用与变种问题7.1 实际交易场景映射这个算法模型可以对应现实中的日内交易限制如A股的T1规则券商对频繁交易的风控限制基金管理的交易频率约束7.2 常见变种问题交易费用版本每次卖出扣除固定手续费修改状态转移方程中的卖出收益项冷却期版本卖出后需要等待一天才能买入增加一个冷却状态维度任意k次交易将本题的k2推广到任意k当kn/2时退化为无限交易版本8. 个人优化心得在实际编码比赛中我总结出几个提速技巧预处理极端情况if len(prices) 2: return 0使用变量名别名hold, cash dp[i-1][k][1], dp[i-1][k-1][0]提前计算重复表达式today_price prices[i]反向遍历交易次数 当k较大时从大到小遍历可以避免状态覆盖问题对于这个特定问题经过多次实践后我发现最可靠的实现方式是严格按照状态机思路明确每个状态的定义和转移条件。在面试中建议先完整写出三维DP的定义再讨论优化空间这样可以展示出对问题的全面理解。
1. 问题背景与核心挑战这道题目在LeetCode股票买卖系列中属于难度分水岭它要求我们在最多完成两笔交易的前提下实现利润最大化。与基础版本只允许一次交易和无限交易版本相比两笔交易的限制使得状态管理复杂度呈指数级增长。我最初看到这个问题时直觉上认为只需要记录第一次买卖和第二次买卖两个状态就够了。但实际编写代码时发现这样的设计无法处理重叠交易时段的情况。比如当第一次卖出和第二次买入发生在同一天时这种状态转换就会变得非常棘手。2. 三维DP的状态定义艺术2.1 状态维度的精确定义正确的状态设计应该包含三个维度天数索引i处理到第几天交易次数k已完成多少次完整交易买入卖出持仓状态0/1当前是否持有股票用dp[i][k][0/1]表示第i天、已完成k次交易、当前持仓状态下的最大利润。这个三维结构完美覆盖了所有可能的情况。关键理解这里的k指已经完成的交易次数而不是正在进行的交易。这是很多初学者容易混淆的点。2.2 状态转移方程推导基于上述定义我们可以建立完整的状态转移关系dp[i][k][0]未持仓可能来自前一天也未持仓dp[i-1][k][0]或者前一天持仓今天卖出dp[i-1][k][1] prices[i]取两者最大值dp[i][k][1]持仓中可能来自前一天已持仓dp[i-1][k][1]或者前一天未持仓今天买入注意k的变化当k 0时dp[i-1][k-1][0] - prices[i]取两者最大值特别注意买入时的k-1操作这表示完成一次完整交易后k才增加。3. 边界条件与初始化技巧3.1 初始状态的设置dp[0][0][0] 0 第0天未持仓利润为0dp[0][0][1] -prices[0] 第0天买入利润为负股价dp[0][1][0] -inf 不可能在第0天已完成1次交易dp[0][1][1] -inf 同上dp[0][2][0] -inf 不可能在第0天已完成2次交易dp[0][2][1] -inf 同上3.2 空间优化策略虽然三维DP直观但实际编码时可以优化为二维数组。因为第i天的状态只依赖于第i-1天所以可以压缩掉天数维度dp [[[0]*2 for _ in range(3)] for _ in range(2)] # 使用模2循环利用空间 for i in range(1, n): for k in range(1, 3): dp[i%2][k][0] max(dp[(i-1)%2][k][0], dp[(i-1)%2][k][1] prices[i]) dp[i%2][k][1] max(dp[(i-1)%2][k][1], dp[(i-1)%2][k-1][0] - prices[i])4. 完整代码实现与逐行解析4.1 Python实现版本def maxProfit(prices): if not prices: return 0 n len(prices) dp [[[0]*2 for _ in range(3)] for _ in range(n)] # 初始化第一天状态 for k in range(3): dp[0][k][0] 0 dp[0][k][1] -prices[0] for i in range(1, n): for k in range(1, 3): # 未持仓状态 dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i]) # 持仓状态 dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) return dp[n-1][2][0]4.2 关键代码解析三维数组初始化dp[i][k][0/1]结构确保覆盖所有状态组合初始资金设为0初始持仓成本为-prices[0]双重循环逻辑外层遍历所有交易日内层遍历可能的交易次数1和2次状态转移实现未持仓状态考虑保持空仓或卖出获利持仓状态考虑保持持仓或新建仓位5. 常见错误与调试技巧5.1 典型错误模式交易次数计算错误错误做法在买入时增加k值正确做法只有在完成完整交易卖出后才增加k状态转移遗漏忘记考虑保持现状的转移路径只考虑改变状态的情况边界条件缺失未处理空输入情况未正确初始化第0天的所有可能状态5.2 调试检查清单当你的DP解法不通过时可以按照以下步骤排查打印DP表的前几行确认状态转移是否符合预期检查k的增减是否发生在正确的操作后验证初始状态是否覆盖所有可能性用简单测试案例如[1,2,3,4,5]手动推算DP表6. 算法复杂度与优化对比6.1 时间与空间分析时间复杂度O(n*k) → O(n)因为k最大为2空间复杂度原始三维DPO(nk2)优化后O(k*2) → O(1)常数空间6.2 替代解法对比峰谷法找出所有利润递增区间取最大的两个问题无法处理重叠交易时段适用场景交易次数无限制时状态机DP定义5个状态未操作、第一次买入、第一次卖出...本质上是对三维DP的另一种表述优点代码更简洁贪心算法尝试记录最小价格和最大利润无法正确处理两笔交易的情况7. 实战应用与变种问题7.1 实际交易场景映射这个算法模型可以对应现实中的日内交易限制如A股的T1规则券商对频繁交易的风控限制基金管理的交易频率约束7.2 常见变种问题交易费用版本每次卖出扣除固定手续费修改状态转移方程中的卖出收益项冷却期版本卖出后需要等待一天才能买入增加一个冷却状态维度任意k次交易将本题的k2推广到任意k当kn/2时退化为无限交易版本8. 个人优化心得在实际编码比赛中我总结出几个提速技巧预处理极端情况if len(prices) 2: return 0使用变量名别名hold, cash dp[i-1][k][1], dp[i-1][k-1][0]提前计算重复表达式today_price prices[i]反向遍历交易次数 当k较大时从大到小遍历可以避免状态覆盖问题对于这个特定问题经过多次实践后我发现最可靠的实现方式是严格按照状态机思路明确每个状态的定义和转移条件。在面试中建议先完整写出三维DP的定义再讨论优化空间这样可以展示出对问题的全面理解。
