《LeetCode 714 买股票的最佳时机含手续费 || LeetCode 123 买卖股票的最佳时机|||》

一、题目

二、做题思路

2.1 状态表示（核心基础）

本题要求计算在无限次交易且每笔交易扣除手续费条件下的最大利润。由于每天结束时存在两种状态——持有股票与不持有股票，我们定义两个状态数组：

• f[i]表示第i天结束后，持有股票（即当天持有股票）的最大利润。

• g[i]表示第i天结束后，不持有股票（即当天空仓）的最大利润。

2.2 状态转移方程（关键难点）

每天可以进行买入、卖出或观望操作，两种状态之间的转移关系如下：

• 持有股票f[i]：可从两种情况转移——（1）前一天就持有f[i-1]（继续持有）；（2）今天买入，必须从前一天空仓g[i-1]转移，并减去今日股价prices[i]。因此f[i] = max(f[i-1], g[i-1] - prices[i])。

• 不持有股票g[i]：可从两种情况转移——（1）前一天就空仓g[i-1]（继续空仓）；（2）今天卖出，必须从前一天持有f[i-1]转移，加上今日股价并扣除手续费fee。因此g[i] = max(g[i-1], f[i-1] + prices[i] - fee)。

2.3 初始化（边界防护）

第 0 天（第一天）的初始状态：

• f[0] = -prices[0]（买入股票，利润为负股价）。

• g[0] = 0（空仓，无交易，利润为 0）。
  若prices为空，直接返回 0，避免越界。

2.4 填表顺序（递推方向）

每个i状态仅依赖i-1的状态，因此必须从左到右（即i从 1 到n-1）依次填充两个数组，确保每个状态计算时，其所有前置状态均已就绪。

2.5 返回值（目标映射）

题目要求返回最大利润。最后一天（下标n-1）不持有股票的利润通常大于等于持有股票的利润（因为持有股票可随时卖出获利），但为严谨，取两者较大值。因此返回max(f[n-1], g[n-1])。

三、代码

class Solution { public: int maxProfit(vector<int>& prices, int fee) { int n = prices.size(); // 边界处理：若无交易日，利润为0 if (n == 0) return 0; // 1. 创建dp表（两个一维数组） // f[i] : 第 i 天结束后，持有股票（即当天持有股票）的最大利润 // g[i] : 第 i 天结束后，不持有股票（即当天空仓）的最大利润 vector<int> f(n); vector<int> g(n); // 2. 初始化（第 0 天） f[0] = -prices[0]; // 第 0 天买入，利润为负的股价 g[0] = 0; // 第 0 天空仓，利润为0 // 3. 填表顺序：从左到右（i 从 1 到 n-1） for (int i = 1; i < n; i++) { // 4. 状态转移方程： // 持有股票：要么前一天就持有（f[i-1]），要么今天买入（从空仓 g[i-1] 转入，减去今日价格） f[i] = max(f[i - 1], g[i - 1] - prices[i]); // 不持有股票：要么前一天就空仓（g[i-1]），要么今天卖出（从持有 f[i-1] 转入，加今日价格并扣除手续费） g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee); } // 5. 返回值：最后一天两种状态的最大利润（卖出后空仓大概率更优，但取两者较大值更严谨） return max(f[n - 1], g[n - 1]); } };

四、流程图

五、题目

六、做题思路

6.1 状态表示（核心基础）

本题要求计算在最多完成两笔交易条件下的最大利润。由于交易次数有限（0、1、2），我们需要同时记录持仓状态和已完成交易次数。因此定义两个二维数组：

• f[i][j]表示第i天结束后，持有股票，并且已经完成了j次交易（即卖出过j次）的最大利润。

• g[i][j]表示第i天结束后，不持有股票，并且已经完成了j次交易的最大利润。
  其中j的取值为 0、1、2，分别对应未完成交易、完成一笔、完成两笔。

6.2 状态转移方程（关键难点）

每天可以选择买入、卖出或观望，且交易次数在卖出时增加（买入不增加次数）。转移关系如下：

• 持有股票f[i][j]：可从两种情况转移——（1）前一天就持有f[i-1][j]（继续持有）；（2）今天买入，必须从前一天不持有且同交易次数j的状态g[i-1][j]转移，并减去今日股价。因此f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i])。

• 不持有股票g[i][j]：可从两种情况转移——（1）前一天就不持有g[i-1][j]（继续空仓）；（2）今天卖出，必须从前一天持有且交易次数为j-1的状态f[i-1][j-1]转移（卖出增加一次交易），并加上今日股价。注意j至少为 1 时才能卖出。因此g[i][j] = max(g[i-1][j], (j>=1 ? f[i-1][j-1] + prices[i] : -INF))。

6.3 初始化（边界防护）

所有状态初始化为负无穷（-INF），表示不可达。第 0 天（第一天）的合理状态为：

• f[0][0] = -prices[0]（买入第一天的股票，持有且交易 0 次）。

• g[0][0] = 0（不持有且交易 0 次，未进行任何操作）。
  其余状态（如f[0][1]、g[0][2]等）保持负无穷，因为第一天不可能完成交易。

6.4 填表顺序（递推方向）

每个i状态仅依赖i-1的状态，且同一i内不同j之间无依赖关系，因此必须按时间从左到右（即i从 1 到n-1）遍历，内部j从 0 到 2 顺序任意。确保每个状态计算时，其所有前置状态均已就绪。

6.5 返回值（目标映射）

题目要求返回最大利润。最后一天（下标n-1）不持有股票的利润一定优于持有状态（因为持有股票可卖出获利），所以只需考虑g[n-1][0]、g[n-1][1]、g[n-1][2]中的最大值。因此返回max(g[n-1][0], g[n-1][1], g[n-1][2])。

七、代码

class Solution { public: int maxProfit(vector<int>& prices) { const int INF = 0x3f3f3f3f; // 定义一个足够大的正数，用于表示负无穷 int n = prices.size(); if (n == 0) return 0; // 边界处理：无交易日 // 1. 创建dp表（两个二维数组） // f[i][j] : 第 i 天结束后，持有股票，并且已经进行了 j 次交易（卖出次数）的最大利润 // g[i][j] : 第 i 天结束后，不持有股票，并且已经进行了 j 次交易（卖出次数）的最大利润 // 其中 j 的取值范围为 0,1,2（最多两笔交易） vector<vector<int>> f(n, vector<int>(3, -INF)); // 初始化为负无穷，表示不可达状态 auto g = f; // 同样初始化 // 2. 初始化（第 0 天） // 持有股票，已交易0次：买入第一天的股票，利润为 -prices[0] f[0][0] = -prices[0]; // 不持有股票，已交易0次：未进行任何操作，利润为 0 g[0][0] = 0; // 其他状态（如 f[0][1], f[0][2] 等）保持负无穷，表示第一天不可能已经完成交易 // 3. 填表顺序：时间从前往后（i 从 1 到 n-1），交易次数 j 从 0 到 2（但内部转移无顺序依赖） for (int i = 1; i < n; i++) { for (int j = 0; j < 3; j++) { // 4. 状态转移方程： // 持有股票状态： // - 前一天就持有：f[i-1][j] // - 今天买入：需要从前一天不持有且同次数 j 的状态转移，减去今日价格 f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]); // 不持有股票状态： // - 前一天就不持有：g[i-1][j]（继承） g[i][j] = g[i - 1][j]; // - 今天卖出：必须从持有状态且交易次数为 j-1 转移（卖出增加一次交易），加上今日价格 if (j >= 1) { g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]); } // 注：若 j=0，则无法从卖出转移（因为还未进行过交易），保持继承状态 } } // 5. 返回值：最后一天不持有股票且交易次数为 0、1、2 三种情况中的最大值 // 因为最终利润最大时必定不持有股票（持有可视为未实现收益，但卖掉会更优或相等） return max({g[n - 1][0], g[n - 1][1], g[n - 1][2]}); } };

八、流程图