本文共 1180 字，大约阅读时间需要 3 分钟。
在股票交易问题中，使用动态规划（DP）是一种有效的方法来找到最大利润。以下是一个优化后的解决方案，模仿了技术人员的写作风格，避免使用AI特有的表达方式。问题描述：我们需要计算从买入股票到卖出的过程中，扣除手续费后的最大利润。DP方法中，dp[i][0]表示第i天不持有股票的最大收益，dp[i][1]表示第i天持有股票的最大收益。通过这个状态机，我们可以跟踪每一天的交易状态。解决方案：因为买入时需要支付手续费，所以特殊处理。到达当天不持有股票的状态时，只能是前一天持有并且卖出，或者前一天不持有。此外，持有股票的时候，可能是今天从不持有变为持有，或者是从持有延续。初始化：dp[0][0] = 0：第0天不持有股票的收益为0。dp[0][1] = -fee - prices[0]：第0天持有股票的收益为第一天购入价格减去手续费。递推关系：当天不持有股票的状态：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])当天持有股票的状态：dp[i][1] = max(dp[i-1][1], dp[i-1][0] - fee - prices[i])最终结果：返回dp[prices.size()-1][0]，即最后一天不持有的最大收益。实现代码：#includeusing namespace std;class Solution {public: int maxProfit(vector & prices, int fee) { vector > dp(prices.size(), vector (2)); dp[0][0] = 0; dp[0][1] = -fee - prices[0]; for(int i = 1; i < prices.size(); ++i) { dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]); dp[i][1] = max(dp[i-1][1], dp[i-1][0] - fee - prices[i]); } return dp[prices.size()-1][0]; }};
这段代码通过动态规划计算了股票交易的最大利润。每一步根据前一天的状态决定当前天的操作，从而最大化利润。对于每一天，计算两种状态的利润：持有和不持有，并选择最优解。
这个方法的时间复杂度为O(n)，空间复杂度为O(n)，适合处理较长的股票价格序列。
转载地址：http://vvjuk.baihongyu.com/