一、题目二、做题思路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(vectorint prices, int fee) { int n prices.size(); // 边界处理若无交易日利润为0 if (n 0) return 0; // 1. 创建dp表两个一维数组 // f[i] : 第 i 天结束后持有股票即当天持有股票的最大利润 // g[i] : 第 i 天结束后不持有股票即当天空仓的最大利润 vectorint f(n); vectorint 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], (j1 ? 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(vectorint 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最多两笔交易 vectorvectorint f(n, vectorint(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]); } // 注若 j0则无法从卖出转移因为还未进行过交易保持继承状态 } } // 5. 返回值最后一天不持有股票且交易次数为 0、1、2 三种情况中的最大值 // 因为最终利润最大时必定不持有股票持有可视为未实现收益但卖掉会更优或相等 return max({g[n - 1][0], g[n - 1][1], g[n - 1][2]}); } };八、流程图