前言

121. Best Time to Buy and Sell Stock
122. Best Time to Buy and Sell Stock II
123. Best Time to Buy and Sell Stock III
188. Best Time to Buy and Sell Stock IV

題目敘述

  • 題目難度：Medium
  • 題目描述： 給定一個整數陣列 prices，其中 prices[i] 代表給定股票在第 i 天的價格，請找到你能獲得的最高股票收益，可以買賣股票多次，但是有以下限制：
    • 當你賣出股票後，隔一天為冷卻期，無法進行買賣
    • 在你買股票前，需要把先前持有的股票賣出 (i.e. 你不能夠 第一天買然後第二天也買，要先把第一天的賣掉)

解法

一開始的想法

這題我後來參考了 NeetCode 的影片，裡面的樹狀圖幫助很大，

Decision Tree

Recursive + Memoization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<vector<int>> dp;
    int helper(vector<int>& prices, int start, int canBuy){
        if(start >= prices.size()) return 0;
        
        
        if(dp[start][canBuy]!= -1) return dp[start][canBuy];

        //Not buy
        int cooldown = helper(prices,start+1, canBuy);

        //Buy
        if(canBuy == 1){
            int sum = -prices[start] + helper(prices,start+1,0);
            dp[start][canBuy] = max(cooldown, sum);
        } 
        // Sell
        else if(canBuy == 0){
            int sum = prices[start]+helper(prices,start+2,1);
            dp[start][canBuy] = max(cooldown, sum);
        }
        
        return dp[start][canBuy];
    }

    int maxProfit(vector<int>& prices){
        if(prices.size()<=1) return 0;
        dp = vector<vector<int>>(prices.size(), vector<int>(2, -1));
        return helper(prices,0, true);
    }
};

首先一樣狀況分成三種，cooldown, buy, sell。如果還沒有買，那當天可以選擇買或冷卻，如果當天買了，那當天可以選擇賣或冷卻。 在 helper 函數中，透過 canBuy 來判斷當天是否可以買，如果可以買那就會是 1 否則就賣出，也就是為 0。由於每天都可以選擇 cooldown 因此在一開始就先 cooldown 然後直接呼叫隔天。回傳結果存放到變數 cooldown當中，而如果當天可以買，則當前總額 sum 會需要扣掉當日價格，也可以看成加上負的當日價格，再加上做這個決定後，後續的遞迴迴呼叫結果 helper(prices, start+1, 0) (參數 0 是因為今天買了，那明天就不能買)。 **接著就需要比較，第一天冷卻還是第一天買入的結果值比較大， max(cooldown, sum)**，這個值會存放到用於儲存重複計算的 dp[start][canBuy] 中。

另一方面，如果當日要賣出，則需要將當日價格加上，這個決定後續的遞迴結果 helper(prices, start+2, 1)，接著一樣與今日冷卻的決策結果 cooldown 去做比較 max(cooldown, sum) 並一樣儲存在 dp[start][canBuy] 當中。 最後回傳 dp[start][canBuy]。

遞迴終止條件，如果超出目前 prices 長度範圍，則回傳 0，另外若有發現重複計算，則回傳計算過的值 dp[start][canBuy]。

執行結果

複雜度

複雜度 結果 說明
時間複雜度 $O(n)$ dp 包含 $n \cdot 2$ 種狀態，其中 $n$ 是價格陣列的大小，每個狀態最多計算一次（使用遞迴函數時會檢查 dp[start][canBuy] 是否已計算），操作僅需常數時間
空間複雜度 $O(n)$ dp 占用 $O(n)$ 空間，儲存每種狀態的結果。遞迴過程中，每次調用函數會使用額外的遞迴棧空間，最深遞迴深度為 $n$，總空間複雜度為 $O(n)$