买卖股票的最佳时机含手续费
贪心算法
将手续费放在买入时进行计算
- 在初始时，buy 的值为prices[0] 加上手续费fee。那么当我们遍历到第(i>0) 天时：
- 如果当前的股票价格prices[i] 加上手续费fee 小于 buy，因此我们将buy 更新为 prices[i]+fee；
- 如果当前的股票价格prices[i] 大于buy，那么我们直接卖出股票并且获得prices[i]−buy 的收益。但实际上，我们此时卖出股票可能并不是全局最优的（例如下一天股票价格继续上升），因此我们可以提供一个反悔操作，看成当前手上拥有一支买入价格为 prices[i] 的股票，将buy 更新为 prices[i]。这样一来，如果下一天股票价格继续上升，我们会获得 prices[i+1]−prices[i] 的收益，加上这一天prices[i]−buy 的收益，恰好就等于在这一天不进行任何操作，而在下一天卖出股票的收益；
- 对于其余的情况，prices[i] 落在区间 [buy−fee,buy] 内，它的价格没有低到我们放弃手上的股票去选择它，也没有高到我们可以通过卖出获得收益，因此我们不进行任何操作。
即当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利。在遍历完整个数组prices 之后之后，我们就得到了最大的总收益。
class Solution { public: int maxProfit(vector<int>& prices, int fee) { int buy = prices[0] + fee; int profit = 0; for (int i = 1; i < prices.size(); i++) { if (prices[i] + fee < buy) { buy = prices[i] + fee; } else if (prices[i] > buy) { profit += prices[i] - buy; buy = prices[i]; } } return profit; } };
动态规划
确定dp数组以及下标的含义
- 0：持有股票（包括之前买的和今天买的）
- 1：不持有股票（包括之前没买和今天卖了）
确定递推公式
- 0：持有股票
dp[i][0] = max( dp[i-1][0] , dp[i-1][2] - prices[i] ); - 1：不持有股票
dp[i][1] = max( dp[i-1][1] , dp[i-1][0] + prices[i] );
初始化
- dp[0][0] = -prices[0] - fee;
- dp[0][1] = 0；
class Solution { public: int maxProfit(vector<int>& prices, int fee) { if(prices.size() <= 1) return 0; vector<vector<int>> dp(prices.size() ,vector<int>(2,0)); dp[0][0] = -prices[0] - fee; dp[0][1] = 0; for(int i=1 ;i<prices.size() ;i++) { dp[i][0] = max(dp[i-1][0] , dp[i-1][1] - prices[i] - fee); dp[i][1] = max(dp[i-1][1] , dp[i-1][0] + prices[i]); } return dp[prices.size()-1][1]; } };
二刷
class Solution { public: int maxProfit(vector<int>& prices, int fee) { vector<vector<int>> dp(prices.size(),vector<int>(2,0)); dp[0][0] = 0; dp[0][1] = -prices[0]; for(int i=1; i<prices.size();i++) { dp[i][0] = max(dp[i-1][0] , dp[i-1][1]+prices[i]-fee); dp[i][1] = max(dp[i-1][1] , dp[i-1][0]-prices[i]); } return max(dp[prices.size()-1][0] , dp[prices.size()-1][1]); } };
