【Classic 150 刷题计划】 LeetCode 123. 买卖股票的最佳时机 III | C++ 状态机动态规划与通用交易拓展

LeetCode 123. 买卖股票的最佳时机 III 题目描述题目级别困难给定一个数组它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。示例 1:输入prices [3,3,5,0,0,3,1,4]输出6解释在第 4 天股票价格 0买入在第 6 天股票价格 3卖出利润 3-0 3 。随后在第 7 天股票价格 1买入在第 8 天 股票价格 4卖出利润 4-1 3 。示例 2:输入prices [1,2,3,4,5]输出4解释在第 1 天买入第 5 天卖出利润 4。示例 3:输入prices [7,6,4,3,1]输出0解释在这个情况下没有交易完成所以最大利润为 0。提示:1 prices.length 10^50 prices[i] 10^5 破题思路状态机 DP (Finite State Machine DP)这道题是整个股票交易问题家族的“分水岭”。通过维护交易轮次kkk与持仓状态持有 / 未持有可以建立状态机转移。1. 状态定义设在第iii天结束时buy[j]当前完成了jjj次买入动作、且手头持有股票时的最大资金收益。sell[j]当前完成了jjj次卖出动作、且手头空仓时的最大资金收益。2. 状态转移方程对于每天的股价price第jjj次交易的状态更新如下进入持仓状态buy[j]可以选择继续保持昨天的持仓buy[j]也可以在上一次卖出空仓sell[j - 1]的基础上按今天价格买入buy[j]max⁡(buy[j],sell[j−1]−price)buy[j] \max(buy[j], sell[j - 1] - price)buy[j]max(buy[j],sell[j−1]−price)进入空仓状态sell[j]可以选择继续保持昨天的空仓sell[j]也可以在当前持仓buy[j]的基础上按今天价格卖出sell[j]max⁡(sell[j],buy[j]price)sell[j] \max(sell[j], buy[j] price)sell[j]max(sell[j],buy[j]price)3. 初始化细节buy数组初始化为负无穷大如INT_MIN或-prices[0]表示初始时在未产生现金流前无法凭空持有股票。sell数组初始化为0表示还没开始交易时本金利润为 0。这种向量化的写法天生具备高度通用性只需将k2k 2k2改为任意正整数即可直接无缝 AC 《LeetCode 188. 买卖股票的最佳时机 IV》最多完成kkk笔交易。 C 代码实现 (原汁原味作者版)classSolution{public:intmaxProfit(vectorintprices){intk2;// buy[i] 表示完成第 i 次买入且持股时的最大利润// sell[i] 表示完成第 i 次卖出且空仓时的最大利润vectorintbuy(k1,INT_MIN),sell(k1,0);for(autoprice:prices){for(inti1;ik;i){buy[i]max(buy[i],sell[i-1]-price);sell[i]max(sell[i],buy[i]price);}}returnsell[k];}};