題目鏈接

貪心

每次只能交易一個(gè)股票，最優(yōu)的選擇就是低買(mǎi)高賣(mài)。不過(guò)每次交易股票都有一次手續(xù)費(fèi)?？梢园咽掷m(xù)費(fèi)算到買(mǎi)入的價(jià)格里。只要能收益就交易。
每次賣(mài)出一個(gè)股票就擁有了原價(jià)購(gòu)買(mǎi)股票的機(jī)會(huì)。這樣就能在具有手續(xù)費(fèi)的前提下低買(mǎi)高賣(mài)。

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;} };

動(dòng)態(tài)規(guī)劃

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;} };

總結(jié)

以上是生活随笔為你收集整理的贪心/动态规划 - 买卖股票的最佳时机含手续费的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。