題目網址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

題意：給一 array prices, 其中 prices[i] 代表第 i 天的股票價格, 在滿足下列條件的前提下, 盡可能地完成更多的交易, 計算出最大利潤。

  • 賣出股票後, 你沒辦法在下一天買入股票(冷凍期為一天)
  • 不能同時參與多筆交易, 必須在再次購買前出售掉之前的股票

Solution 1：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 prices 前先加上一個 0, 代表什麼元素都沒有的狀態
  • rest[i] 代表第 i 天手上未持有股票, 且狀態為 rest 的最大收益
  • hold[i] 代表第 i 天手上持有股票, 且狀態為 hold 的最大收益
    （手上持有股票然後休息, 其狀態仍是 hold。rest 狀態必須在未持有股票時）
  • sold[i] 代表第 i 天手上未持有股票, 且狀態為 sold 的最大收益

2. 根據下圖, 可得狀態轉移方程：

  • rest[i] = max(rest[i - 1], sold[i - 1])

  • hold[i] = max(hold[i - 1], rest[i - 1] - prices[i])

  • sold[i] = hold[i - 1] + prices[i]

3. 初始化：

  • hold[0]、sold[0]、rest[0]：沒有股票時, 最大利潤為 0
  • hold[1]：第一天買入 ➔ 此時最大利潤為 prices[1]
  • sold[1]：第一天買入, 並且賣出 ➔ 此時最大利潤為 0
  • rest[1]：第一天不操作 ➔ 此時最大利潤為 0
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        const int n = prices.size();
        vector<int> hold(n + 1, 0), sold(n + 1, 0), rest(n + 1, 0);

        prices.emplace(prices.begin(), 0);
        hold[1] = -prices[1];

        for (int i = 2; i <= n; ++i) {
            rest[i] = max(sold[i - 1], rest[i - 1]);
            hold[i] = max(hold[i - 1], rest[i - 1] - prices[i]); // 買入股票, 收益減少
            sold[i] = hold[i - 1] + prices[i]; // 賣出股票, 收益增加
        }

        // 最大利潤不可能出現在 buy 而未 sell 的時候, 所以不考慮最後一天為 hold 的狀態
        return max(rest.back(), sold.back());
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(n)$ ➔ hold, sell 和 rest

Solution 2：

想法：改進 Solution 1, 因為 hold[i]、sold[i]、rest[i] 只會用到 i - 1 的狀態, 因此只要儲存 i - 1 的狀態即可, 根本不需要開到 $O(n)$ space

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        const int n = prices.size();

        prices.emplace(prices.begin(), 0);

        int hold = -prices[1], sold = 0, rest = 0;

        for (int i = 2; i <= n; ++i) {
            int prevHold = hold, prevSold = sold, prevRest = rest;
            rest = max(prevRest, prevSold);
            hold = max(prevHold, prevRest - prices[i]);
            sold = prevHold + prices[i];
        }

        return max(rest, sold);
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(1)$ ➔ 只需常數空間