0309. 最佳買賣股票時機含冷凍期 · ttttt

# 0309. 最佳買賣股票時機含冷凍期 ## 題目地址(309. 最佳買賣股票時機含冷凍期) <https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個整數數組，其中第 i 個元素代表了第 i 天的股票價格。設計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）: 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。示例: 輸入: [1,2,3,0,2] 輸出: 3 解釋: 對應的交易狀態為: [買入, 賣出, 冷凍期, 買入, 賣出] ``` ``` ## 前置知識 - [動態規劃](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 公司 - 阿里 - 騰訊 - 字節 ## 思路這是一道典型的 DP 問題， DP 問題的核心是找到狀態和狀態轉移方程。這道題目的狀態似乎比我們常見的那種 DP 問題要多，這里的狀態有 buy sell cooldown 三種，我們可以用三個數組來表示這這三個狀態，buy,sell, cooldown. - buy\[i\]表示第 i 天，且以 buy 結尾的最大利潤 - sell\[i\]表示第 i 天，且以 sell 結尾的最大利潤 - cooldown\[i\]表示第 i 天，且以 sell 結尾的最大利潤我們思考一下，其實 cooldown 這個狀態數組似乎沒有什么用，因此 cooldown 不會對`profit`產生任何影響。我們可以進一步縮小為兩種狀態。 - buy\[i\] 表示第 i 天，且以 buy 或者 coolwown 結尾的最大利潤 - sell\[i\] 表示第 i 天，且以 sell 或者 cooldown 結尾的最大利潤對應的狀態轉移方程如下： > 這個需要花點時間來理解 ``` <pre class="calibre18">``` buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]); sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]); ``` ``` 我們來分析一下，buy\[i\]對應第 i 的 action 只能是 buy 或者 cooldown。 - 如果是 cooldown，那么 profit 就是 buy\[i - 1\] - 如果是 buy，那么就是`前一個賣的profit減去今天買股票花的錢`，即 sell\[i -2\] - prices\[i\] > 注意這里是 i - 2，不是 i-1 ，因為有 cooldown 的限制 sell\[i\]對應第 i 的 action 只能是 sell 或者 cooldown。 - 如果是 cooldown，那么 profit 就是 sell\[i - 1\] - 如果是 sell，那么就是`前一次買的時候獲取的利潤加上這次賣的錢`，即 buy\[i - 1\] + prices\[i\] ## 關鍵點解析 - 多狀態動態規劃 ## 代碼 ``` <pre class="calibre18">``` /* * @lc app=leetcode id=309 lang=javascript * * [309] Best Time to Buy and Sell Stock with Cooldown * */ /** * @param {number[]} prices * @return {number} */ var maxProfit = function (prices) { if (prices == null || prices.length <= 1) return 0; // 定義狀態變量 const buy = []; const sell = []; // 尋常 buy[0] = -prices[0]; buy[1] = Math.max(-prices[0], -prices[1]); sell[0] = 0; sell[1] = Math.max(0, prices[1] - prices[0]); for (let i = 2; i < prices.length; i++) { // 狀態轉移方程 // 第i天只能是買或者cooldown // 如果買利潤就是sell[i - 2] - prices[i], 注意這里是i - 2，不是 i-1 ，因為有cooldown的限制 // cooldown就是buy[i -1] buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]); // 第i天只能是賣或者cooldown // 如果賣利潤就是buy[i -1] + prices[i] // cooldown就是sell[i -1] sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]); } return Math.max(buy[prices.length - 1], sell[prices.length - 1], 0); }; ``` ``` ## 相關題目 - [121.best-time-to-buy-and-sell-stock](121.best-time-to-buy-and-sell-stock.html) - [122.best-time-to-buy-and-sell-stock-ii](122.best-time-to-buy-and-sell-stock-ii.html)