最大利润两笔交易：AlgoNote 深度拆解「买卖股票的最佳时机 III」动态规划

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇技术指南聚焦于 AlgoNote 仓库中 LeetCode **第 123 题「买卖股票的最佳时机 III」**的完整解题链路如何在最多完成两笔交易、且不能同时参与多笔交易的约束下用动态规划求出最大利润。读完本文你将掌握按交易日 × 交易状态二维 DP 的状态设计、五状态转移方程的推导过程、边界初始化与最终答案的选取逻辑并理解它与第 121、122、188 题构成的股票买卖 DP 系列在状态维度上的递进关系。一、题目背景与核心约束本题对应的题解文档位于 best-time-to-buy-and-sell-stock-iii.md标签为数组、动态规划难度为困难。给定一个数组prices代表一只股票其中prices[i]代表这只股票第i天的价格。最多可完成两笔交易且不能同时参与多笔交易必须在再次购买前出售掉之前的股票。要求计算所能获取的最大利润。与仅允许一笔交易的 第 121 题 相比本题的难点在于交易次数有了上限最多两笔可以是零笔、一笔或两笔交易之间存在先后约束第二次买入必须发生在第一次卖出之后即状态之间存在严格的顺序依赖不能通过简单的前后缀拆分直接套用单次交易的贪心/递推虽然第一笔交易在某个分割点之前、第二笔在之后的拆解法可行但动态规划的状态机建模是更通用、更易推广到任意k笔交易的方案。二、状态设计五状态刻画每天结束时的持仓情况最多可完成两笔交易意味着总共有三种情况买卖一次、买卖两次、不买卖。具体到每一天结束账户可能处于5 种状态状态编号状态含义0未进行任何买卖1第一次买入状态2第一次卖出状态3第二次买入状态4第二次卖出状态定义状态dp[i][j]表示第i天处于第j种情况0 j 4下所获取的最大利润。这里需要特别强调一个容易混淆的点原文档明确指出第j种情况并不代表这一天一定要发生买入或卖出操作而是描述这一天结束时账户所处的买入/卖出状态。例如前一天完成了第一次买入第二天没有任何操作那么第二天就沿用前一天的第一次买入状态。这正是 DP 状态机建模中状态持续的含义——dp[i][j]记录的始终是截止到第i天为止该状态下的最优利润。这种按天数阶段线性推进、每个阶段维护多个状态的建模方式正是仓库 线性 DP 章节 所定义的线性动态规划阶段按时间顺序线性划分每个阶段的状态取值只依赖前一阶段。而定义状态 → 推导状态转移方程 → 确定初始条件与边界 → 求解最终结果的四步法也与 动态规划基础章节 中归纳的动态规划解题范式完全一致。三、状态转移方程每个状态如何由前一天推出接下来确定状态转移公式。由于状态之间存在严格的先后顺序买入必须在卖出之前第二次买入必须在第一次卖出之后每个非0状态都可以由两种来源推出取较大者状态0未进行任何买卖不进行任何交易利润恒为0直接继承昨天的状态dp[i][0] dp[i - 1][0]状态1第一次买入状态不做任何操作沿用前一天第一次买入状态的最大利润dp[i][1] dp[i - 1][1]当天发生第一次买入用当前价prices[i]买入现金减少dp[i][1] dp[i - 1][0] - prices[i]取两者较大值dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i])状态2第一次卖出状态不做任何操作沿用前一天第一次卖出状态dp[i][2] dp[i - 1][2]当天发生第一次卖出以当前价卖出现金增加dp[i][2] dp[i - 1][1] prices[i]取两者较大值dp[i][2] max(dp[i - 1][2], dp[i - 1][1] prices[i])状态3第二次买入状态不做任何操作沿用前一天第二次买入状态dp[i][3] dp[i - 1][3]当天发生第二次买入必须先处于第一次已卖出状态dp[i][3] dp[i - 1][2] - prices[i]取两者较大值dp[i][3] max(dp[i - 1][3], dp[i - 1][2] - prices[i])状态4第二次卖出状态不做任何操作沿用前一天第二次卖出状态dp[i][4] dp[i - 1][4]当天发生第二次卖出dp[i][4] dp[i - 1][3] prices[i]取两者较大值dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i])观察这组方程可以提炼出一个通用规律所有买入状态1、3的转移形如max(继承, 前一状态 - prices[i])所有卖出状态2、4的转移形如max(继承, 前一状态 prices[i])。买入用减现金流出卖出用加现金流入而前一状态恰好是顺序上紧邻它的那个状态买入前必须先卖出卖出前必须先买入。这一规律正是后续第 188 题推广到k笔交易时的核心模式。四、边界初始化第一天的五种状态下面确定初始化的边界值。以第0天第一天为起点状态0第一天不做任何操作dp[0][0] 0状态1第一天第一次买入花掉prices[0]利润为负dp[0][1] -prices[0]状态2第一次卖出可视为当天买卖、价格没有变化无盈利dp[0][2] 0状态3第二次买入同样是dp[0][3] -prices[0]状态4第二次卖出同样视作无盈利dp[0][4] 0。注意原文档代码中实际只显式初始化了dp[0][1]和dp[0][3]为-prices[0]其余状态由于 Python 中dp数组整体初始化为0已经天然满足上述边界dp[0][0] dp[0][2] dp[0][4] 0。为什么-prices[0]这种亏损初始化是必要的因为状态1与3代表已持有股票的持仓状态其利润表达式是现金余额视角——买入后现金减少。若初始化为0后续dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])会在尚未买入时错误地允许空仓却记持仓利润导致状态语义被破坏。五、最终答案为什么取dp[size - 1][4]在递推结束后最大利润一定落在无操作状态 0、第一次卖出状态 2、第二次卖出状态 4这三种空仓且交易已了结的状态中且为其中最大值。由于转移过程中始终维护的是最大值而任何卖出的利润都大于等于0当天买卖利润为 0低买高卖利润为正因此dp[size - 1][2] 0dp[size - 1][4] 0如果最优方案实际只需要一笔交易甚至不交易那么在转移时我们允许同一天内完成两笔交易一笔交易的状态可以平滑转移到两笔交易状态dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i])中dp[i-1][3]可以从dp[i-1][2]第一次卖出推导而来而dp[i-1][2]本身已经包含了最优的单笔交易利润。因此最终答案可以直接取dp[size - 1][4]无需再对dp[size - 1][2]和dp[size - 1][4]做额外取最大值。size为股票天数数组长度。六、完整可运行代码原文档给出的标准解法如下List[int]需要from typing import List支持实际提交到力扣平台时注解已由平台预置class Solution: def maxProfit(self, prices: List[int]) - int: size len(prices) if size 0: return 0 dp [[0 for _ in range(5)] for _ in range(size)] dp[0][1] -prices[0] dp[0][3] -prices[0] for i in range(1, size): dp[i][0] dp[i - 1][0] dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i]) dp[i][2] max(dp[i - 1][2], dp[i - 1][1] prices[i]) dp[i][3] max(dp[i - 1][3], dp[i - 1][2] - prices[i]) dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i]) return dp[size - 1][4]代码与状态转移方程一一对应dp表的行数等于天数列数为 5五种状态。dp[0][0]、dp[0][2]、dp[0][4]依赖数组初始化的0值因此代码中只显式设置了两个买入状态的负利润初始值。七、复杂度分析时间复杂度$O(n)$其中n是数组prices的元素个数。只需按天做一次线性遍历每天执行常数次5 次状态转移。空间复杂度$O(n)$。使用了一个size × 5的二维数组dp保存全部状态。空间优化从源码结构可以推断的进阶写法观察转移方程可以发现第i天的所有状态只依赖第i - 1天的状态因此可以用 5 个滚动变量替代二维数组将空间复杂度降至 $O(1)$class Solution: def maxProfit(self, prices: List[int]) - int: size len(prices) if size 0: return 0 # 五个状态变量对应五状态初始化 dp0, dp1, dp2, dp3, dp4 0, -prices[0], 0, -prices[0], 0 for i in range(1, size): new_dp1 max(dp1, dp0 - prices[i]) new_dp2 max(dp2, dp1 prices[i]) new_dp3 max(dp3, dp2 - prices[i]) new_dp4 max(dp4, dp3 prices[i]) # dp0 恒为 0无需更新 dp1, dp2, dp3, dp4 new_dp1, new_dp2, new_dp3, new_dp4 return dp4注意滚动变量更新时需要使用前一天的旧值参与计算因此引入new_*临时变量后统一赋值避免同一天内新值覆盖旧值导致的状态串扰例如dp3需要用到旧的dp2而dp2在同轮已被新值更新。八、算法脉络从一笔交易到任意 k 笔交易的 DP 家族本题不是孤立的它在仓库的题解体系中处于股票买卖 DP 系列的承上启下位置0121. 买卖股票的最佳时机简单只允许1 笔交易用两个变量minprice/maxprofit一趟遍历即可求解本质上是单状态递推0122. 买卖股票的最佳时机 II中等不限交易次数贪心累加所有正差价sum(max(0, prices[i] - prices[i-1]))或者用持有 / 空仓两状态 DP 求解[0123. 买卖股票的最佳时机 III]本文困难最多2 笔交易引入5 状态二维 DP0188. 买卖股票的最佳时机 IV困难最多k 笔交易将 5 状态推广为2 * k 1状态偶数序号表示买入、奇数序号表示卖出转移方程统一为买入j为奇数dp[i][j] max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i])卖出j为偶数dp[i][j] max(dp[i - 1][j], dp[i - 1][j - 1] prices[i])初始时对j 1, 3, ..., 2k - 1的奇数买入状态赋-prices[0]最终答案为dp[size - 1][2 * k]。从源码结构看第 188 题的题解文档中明确写到这道题是 0123 的升级版不过思路一样可见 123 题正是理解这一系列状态机建模的关键入口。此外该系列还有两个带附加条件的变体加入冷冻期的 0309 最佳买卖股票时机含冷冻期 与加入手续费的 0714 最佳买卖股票时机含手续费。它们同样采用买入/卖出状态机建模只是在转移方程中额外处理冷却一天或卖出时扣除手续费的约束。仓库的完整题解索引可参见 docs/solutions/0100-0199/index.md股票买卖系列的四道核心题目0121、0122、0123、0188均收录于其中各道题的归档列表还可在 题解列表 与 分类列表 中按需查阅。九、小结回顾本题的完整求解链条约束识别最多两笔交易且不能同时持仓 → 决定用交易次数 × 持仓状态建模状态定义dp[i][j]表示第i天处于第j种状态0 未买卖、1 首买、2 首卖、3 二买、4 二卖的最大利润转移方程每个状态 max(昨天同状态继承, 昨天前驱状态 ± prices[i])买入减价、卖出加价边界初始化第一天买入状态初始化为-prices[0]卖出状态初始化为0最终答案由于一笔交易可以无缝转移到两笔交易状态直接返回dp[size - 1][4]即可。掌握了这五步你不仅能独立解决本题还能顺势推导出任意k笔交易的第 188 题、以及带冷冻期/手续费的各种变体——这正是状态机式动态规划在股票买卖问题家族中的通用威力所在。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐GitHub_Trending/leetcode1/leetcode买卖股票的最佳时机III动态规划的多状态定义GitHub_Trending/leetcode1/leetcode买卖股票的最佳时机III动态规划的多状态定义 问题定义与场景分析 给定一个数组 price示例工程教程QtBitcoinTrader核心功能揭秘支持Binance/Bitfinex等主流交易所的秘密QtBitcoinTrader核心功能揭秘支持Binance/Bitfinex等主流交易所的秘密 QtBitcoinTrader是一款安全的多加密货币交易所交金融科技桌面应用LeetCode-Book 题解121. 买卖股票的最佳时机——一次遍历贪心求最大利润LeetCode Book 题解121. 买卖股票的最佳时机——一次遍历贪心求最大利润 导读 本文围绕 LeetCode Book 仓库中《Krahets 笔示例工程上一篇从 Hugging Face 到 MLXLFM2.5-1.2B-Thinking-8bit 格式转换原理与实战下一篇如何永久保存微信聊天记录WeChatMsg完整指南帮你掌控数字记忆创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考