714 买卖股票的最佳时机含手续费

题目给定一个整数数组 prices其中 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思路和122不限次买卖股票类似但是卖出的情况中有一个变化卖出的第二种情况变为了前一天持有股票pricesi-fee因为不限制交易次数所以无需展开dp数组代码class Solution{public: int maxProfit(vectorintprices, int fee){intdataprices.size();//0持有1不持有 vectorvectorintdp(data,vectorint(2,0));dp[0][0]-prices[0];dp[0][1]0;for(inti1;idata;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]prices[i]-fee);}returndp[data-1][1];}};二维dp性能不一定是最好的但是一定是最通用的方法。