121. 买卖股票的最佳时机
给定一个数组
prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回
0。
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); // 1. 定义二维 DP 数组 // dp[i][0]：第 i 天，不持有股票的最大现金（默认初始化为 0 没毛病） // dp[i][1]：第 i 天，持有股票的最大现金 // dp[i][2]：第 i 天，今天刚卖出股票的最大现金 vector<vector<int>> dp(n, vector<int>(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(vector<int>& prices) { int n = prices.size(); vector<vector<int>> dp(n, vector<int>(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(vector<int>& prices) { int n = prices.size(); // 精简且精准的四状态划分： // 0: 无操作（未发生交易，全程为0，无需记录） // 1: 第一次持有股票 // 2: 第一次卖出股票（完成第一笔交易） // 3: 第二次持有股票 // 4: 第二次卖出股票（完成第二笔交易） vector<vector<int>> dp(n, vector<int>(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，内层循环套用这两个公式即可。
