Leetcode 連結

概念

每一天我們都有兩種選擇：持有股票，或是賣出股票。

持有股票代表我們在之前某天買入，或是今天才買入。
賣出股票代表我們手上仍持有先前交易留下的現金，或是今天剛賣出股票。
要有效率地解這題，可以使用動態規劃。

理解題目

給定陣列 prices，其中 prices[i] 代表第 i 天的股價，以及整數 fee 代表交易手續費。我們的目標是在每次賣出股票都需支付手續費的前提下，透過多次交易取得最大利潤。

prices = [1,3,2,8,4,9], fee = 2

初步想法

一開始，我們可能會這樣定義 dp[i]：

  • 買入股票：dp[i] = dp[i-1] - prices[i]
  • 賣出股票：dp[i] = dp[i-1] + prices[i] - fee
  • 不動作：dp[i] = dp[i-1]

但這個做法是錯的，因為要賣出股票，必須先前已經買入並持有。這代表我們需要追蹤兩個獨立的狀態：

  • hold[i] – 第 i 天持有股票時的最大利潤
  • cash[i] – 第 i 天未持有股票（即持有現金）時的最大利潤

狀態轉移方程式

由於我們可以選擇繼續持有或買入新股票，狀態轉移如下：

  • 買入股票：
    hold[i] = max(hold[i-1], cash[i-1] - prices[i])
    （要嘛延續前一天的持有狀態，要嘛用手上的現金買入新股票。）
  • 賣出股票：
    cash[i] = max(cash[i-1], hold[i-1] + prices[i] - fee)
    （要嘛保留昨天的現金，要嘛賣出持有的股票，獲利扣除手續費。）
  • 不動作：
    • hold[i] = hold[i-1]（今天不買，持有狀態的值不變。）
    • cash[i] = cash[i-1]（今天不賣，現金狀態的值不變。）

實作

我們建立 hold 和 cash 兩個陣列，儲存 n 天中每個狀態的值：

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int [] hold = new int[n];
        int [] cash = new int[n];

        hold[0] = -prices[0];
        cash[0] = 0;

        for (int i = 1; i < n; i++) {
            hold[i] = Math.max(hold[i-1], cash[i-1] - prices[i]);
            cash[i] = Math.max(cash[i-1], hold[i-1] + prices[i] - fee);
        }
        return cash[n-1];
        
    }
}