121. 买卖股票的最佳时机给定一个数组prices它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回0。class Solution { public: int maxProfit(vectorint prices) { int n prices.size(); // 1. 定义二维 DP 数组 // dp[i][0]第 i 天不持有股票的最大现金默认初始化为 0 没毛病 // dp[i][1]第 i 天持有股票的最大现金 // dp[i][2]第 i 天今天刚卖出股票的最大现金 vectorvectorint dp(n, vectorint(3, 0)); // 2. 初始化第 0 天的特殊状态 // 第 0 天不持有现金是 0 (默认值) // 第 0 天持有说明第 0 天买入现金是 -prices[0] dp[0][1] -prices[0]; // 3. 状态转移 for(int i 1; i n; i){ // 状态 1今天持有股票 // 情况 A昨天就持有了今天啥也不干 (dp[i-1][1]) // 情况 B昨天不持有今天刚买入。因为本题只能交易一次所以买入前的现金必须是初始的 0即 -prices[i] dp[i][1] max(dp[i-1][1], -prices[i]); // 状态 2今天卖出股票不持有了 // 只有唯一一种情况昨天必须持有股票今天把它卖了 dp[i][2] max(dp[i-1][2], dp[i-1][1] prices[i]); } // 4. 返回结果 // 最后一天要想收益最大肯定手里不能捏着股票要么是状态0要么是状态2 return dp[n-1][2]; } };总结1. 状态拆分把“不持有股票”这个状态拆分成dp[i][0]一直没买/之前卖了和dp[i][2]今天刚卖。虽然在这道只交易一次的题里dp[i][0]全程都是 0显得有点“多余”。2. 题目的限制只能买卖一次在推导dp[i][1]持有股票时很多从“多次交易”倒退回来的人会写成max(dp[i-1][1], dp[i-1][0] - prices[i])。这里写成max(dp[i-1][1], -prices[i])。因为只能买一次所以无论哪天买支出前面永远没有“之前卖掉赚到的利润”做铺垫只能是纯粹的减去当天的股价。122. 买卖股票的最佳时机 II给你一个整数数组prices其中prices[i]表示某支股票第i天的价格。在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。然而你可以在 同一天 多次买卖该股票但要确保你持有的股票不超过一股。返回你能获得的 最大 利润。class Solution { public: int maxProfit(vectorint prices) { int n prices.size(); vectorvectorint dp(n, vectorint(3, 0)); dp[0][1] -prices[0]; for(int i 1; i n; i){ // 状态 1持有股票 // 情况 A昨天就持有 // 情况 B昨天刚卖出dp[i-1][2]今天拿着赚到的利润再次买入 dp[i][1] max(dp[i-1][1], dp[i-1][2] - prices[i]); // 状态 2今天卖出股票 dp[i][2] max(dp[i-1][2], dp[i-1][1] prices[i]); } return dp[n-1][2]; } };总结1. 核心差异买入成本的逻辑变迁对比仅限一次交易的 121 题本题的代码仅在一处发生了实质性的修改由-prices[i]变为了dp[i-1][2] - prices[i]。单次交易买入时不存在历史利润必须以初始本金0支付因此成本固定为prices[i]。多次交易买入时可以使用之前卖出股票所累积的利润dp[i-1][2]进行抵扣。这保证了利润可以滚雪球式复投。2. 三维状态机的架构优势该解法保留了将“不持有股票”细分为dp[i][0]从未交易和dp[i][2]刚卖出的设计。虽然在多次无限制交易中dp[i][0]全程为 0 且未参与计算可以简化为标准的二维 0-1 状态机但这种将状态发生瞬间独立抽象的代码架构在面对后续复杂变种如加入冷冻期、手续费时具备极高的可扩展性避免了状态间的逻辑混淆。123. 买卖股票的最佳时机 III给定一个数组它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。class Solution { public: int maxProfit(vectorint prices) { int n prices.size(); // 精简且精准的四状态划分 // 0: 无操作未发生交易全程为0无需记录 // 1: 第一次持有股票 // 2: 第一次卖出股票完成第一笔交易 // 3: 第二次持有股票 // 4: 第二次卖出股票完成第二笔交易 vectorvectorint dp(n, vectorint(5, 0)); // 初始化第 0 天无论是第一次买入还是第二次买入成本都是 prices[0] dp[0][1] -prices[0]; dp[0][3] -prices[0]; for(int i 1; i n; i){ // 状态 1第一次持有 // 延续持有 OR 从初始状态(0)买入 dp[i][1] max(dp[i-1][1], -prices[i]); // 状态 2第一次卖出 // 延续卖出 OR 第一次持有状态今天卖出 dp[i][2] max(dp[i-1][2], dp[i-1][1] prices[i]); // 状态 3第二次持有 // 延续持有 OR 第一次卖出后用第一笔利润回血今天再次买入 dp[i][3] max(dp[i-1][3], dp[i-1][2] - prices[i]); // 状态 4第二次卖出 // 延续卖出 OR 第二次持有状态今天卖出 dp[i][4] max(dp[i-1][4], dp[i-1][3] prices[i]); } // 最多交易两次最大收益必然落在“第二次卖出”状态 return dp[n-1][4]; } };总结1. 利润复用的传递链该解法的核心脉络在于dp[i-1][2]这个节点的承上启下作用dp[i][2]结算了第一笔交易的利润。dp[i][3] max(..., dp[i-1][2] - prices[i])将第一笔利润作为本金投入到第二次买入中。这就形成了一条完美的利润滚雪球链条彻底解决了多次交易时“本金如何计算”的痛点。2. 结构的普适性仔细观察这四个递推公式会发现它们呈现出极其规律的奇偶交替特征奇数状态买入dp[i][j] max(dp[i-1][j], dp[i-1][j-1] - prices[i])偶数状态卖出dp[i][j] max(dp[i-1][j], dp[i-1][j-1] prices[i])发现这个规律后无论题目要求最多交易 3 次、4 次还是 kk 次根本不需要再推导具体逻辑直接写一个外层循环 kk内层循环套用这两个公式即可。