题目链接
贪心
每次只能交易一个股票,最优的选择就是低买高卖。不过每次交易股票都有一次手续费。可以把手续费算到买入的价格里。只要能收益就交易。
每次卖出一个股票就拥有了原价购买股票的机会。这样就能在具有手续费的前提下低买高卖。
class Solution {public:int maxProfit(vector<int>& prices, int fee) {int profit = 0;int buy = prices[0] + fee;for (int i = 1; i < (int)prices.size(); ++i) {if (prices[i] > buy) {profit += prices[i] - buy;buy = prices[i];}else if (prices[i] + fee < buy){buy = prices[i] + fee;}}return profit;}};
动态规划
class Solution {public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();vector<vector<int>> dp(n, vector<int>(2, 0));dp[0][1] = -prices[0];for (int i = 1; i < n; ++i) {dp[i][0] = max(dp[i-1][1] + prices[i] - fee, dp[i-1][0]);dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1]);}return dp[n-1][0];}};
class Solution {public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();int buy = -prices[0];int sell = 0;for (int i = 1; i < n; ++i) {buy = max(buy, sell - prices[i]);sell = max(sell, buy + prices[i] - fee);}return sell;}};
如果觉得《贪心/动态规划 - 买卖股票的最佳时机含手续费》对你有帮助,请点赞、收藏,并留下你的观点哦!