题目
给定一个整数数组prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3 输出：6
解题
方法一：动态规划
class Solution { public: int maxProfit(vector<int>& prices, int fee) { int dp0=0; //无持股 剩下的钱 int dp1=-prices[0];//持股 剩下的钱 for(int i=1;i<prices.size();i++){ dp0=max(dp0,dp1+prices[i]-fee);//统一在卖股票的时候扣除手续费 dp1=max(dp1,dp0-prices[i]); } return dp0; } };
方法二：贪心
class Solution { public: int maxProfit(vector<int>& prices, int fee) { int result = 0; int minPrice = prices[0]; // 记录最低价格 for (int i = 1; i < prices.size(); i++) { // 情况二：相当于买入 if (prices[i] < minPrice) minPrice = prices[i]; // 情况三：保持原有状态（因为此时买则不便宜，卖则亏本） if (prices[i] >= minPrice && prices[i] <= minPrice + fee) { //这行可以不要 continue; } // 计算利润，可能有多次计算利润，最后一次计算利润才是真正意义的卖出 if (prices[i] > minPrice + fee) { result += prices[i] - minPrice - fee; minPrice = prices[i] - fee; // 情况一，这一步很关键 } } return result; } };
其中minPrice = prices[i] - fee;是为了防止在一次买卖中重复扣手续费，只有在 一次买卖的第一次收益中扣费，比如[1,3,5,8,4,11], 价格为1的时候买入，价格为8的时候卖出。那么比如到价格为3的时候，其实已经扣除了手续费，
在这一步中result += prices[i] - minPrice - fee;，但是到后续价格为8前，由于minPrice=prices[i]-fee,使得result += prices[i] - minPrice - fee;变成result+=prices[i]-(prices[i-1]-fee)-fee，从而使得这一次买卖中，不计算手续费。
当出现if (prices[i] < minPrice) minPrice = prices[i];的时候，相当于又是一次新的买卖了，开始了，在新的买卖的第一次收益中会扣除手续费。
也就是说1,3,5,8作为一次交易，在价格为3的时候已经扣除了手续费，
第一次收益：3-1-fee
第二次收益：5-3
第三次收益：8-5
此次买卖收益：8-1-fee
