買賣股票系列

【leetcode】40-best-time-to-buy-and-sell-stock 力扣 121. 買賣股票的最佳時機

【leetcode】41-best-time-to-buy-and-sell-stock-ii 力扣 122. 買賣股票的最佳時機 II

【leetcode】42-best-time-to-buy-and-sell-stock-iii 力扣 123. 買賣股票的最佳時機 III

【leetcode】43-best-time-to-buy-and-sell-stock-iv 力扣 188. 買賣股票的最佳時機 IV

【leetcode】44-best-time-to-buy-and-sell-stock-with-cooldown 力扣 309. 買賣股票的最佳時機包含冷凍期

【leetcode】45-best-time-to-buy-and-sell-stock-with-cooldown 力扣 714. 買賣股票的最佳時機包含手續費

開源地址

為了便於大家學習，所有實現均已開源。歡迎 fork + star~

https://github.com/houbb/leetcode

題目

給定一個整數數組 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

提示：

1 <= prices.length <= 5 * 10^4

1 <= prices[i] < 5 * 10^4

0 <= fee < 5 * 10^4

v1-個人思路-錯誤思路

思路

這一題是 T122 的變種，我們只需要把價格+手續費就行？

利潤在賣出的時候支付？

實現

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int maxProfit = 0;

        for(int i = 1; i < prices.length; i++) {
            int profit = prices[i] - prices[i-1] - fee;
            if(profit > 0) {
                maxProfit += profit;
            }
        }

        return maxProfit;
    }
}

結果

這個實際上是錯誤的。

錯誤的原因是如果一個價格從低到高，中間的的跌宕不能覆蓋 FEE。我們多次交易反而會導致整體的收益下降。

1 4 5 9

比如這種兩次交易利潤：

4-1-2=1
9-5-2=2

就不如直接一次

9-1-2=6

所以應該修正一下，利用我們 T122 DP 的解法。

v2-DP 思路

DP 考量

分為兩個數組：

i 代表第 i 次的操作，可以是買入，也可以是賣出，或者什麼都不做。

其實可以分為兩個狀態數組：

buy[i] 持有

sell[i] 是否賣出後的狀態

遞推公式

// 是否賣出？  不賣； 賣出=上一次買入 + 當前價格
// 是否買？   不買； 買入=上一次賣出-當前價格

初始化

buy[0] = -prices[0]
sell[0] = 0;

代碼

class Solution {
    
    public int maxProfit(int[] prices, int fee) {
        int buy[] = new int[prices.length];
        int sell[] = new int[prices.length];

        buy[0] = -prices[0];

        // 遍歷
        for(int i = 1; i < prices.length; i++) {
            //賣出 不賣出？ 賣出 = buy[i-1] + prices[i] - FEE
            sell[i] = Math.max(sell[i-1], buy[i-1] + prices[i] - fee);

            // 賣出 不賣出？ 賣出 = sell[i-1] - prices[i]
            buy[i] = Math.max(buy[i-1], sell[i-1] - prices[i]);
        }

        return sell[prices.length-1];
    }
    
}

小結

這樣，我們就完成了買賣股票比較完整的整個系列。

最核心的還是 DP，基本可以從頭到尾。

參考資料

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-...