力扣309——最佳買賣股票時機含冷凍期
- 2020 年 2 月 13 日
- 筆記
這道題主要涉及狀態轉移方程，想清楚所有狀態後，就可以輕鬆解決。
原題
給定一個整數數組，其中第 i 個元素代表了第 i 天的股票價格 。
設計一個演算法計算出最大利潤。在滿足以下約束條件下，你可以儘可能地完成更多的交易（多次買賣一支股票）:
- 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
- 賣出股票後，你無法在第二天買入股票 (即冷凍期為 1 天)。
示例:
輸入: [1,2,3,0,2] 輸出: 3 解釋: 對應的交易狀態為: [買入, 賣出, 冷凍期, 買入, 賣出]
原題url：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
解題
暴力解法
一開始我就是想著一共有幾種狀態，這幾種狀態分別可以轉換為哪些狀態：
- 當前是"持股狀態"，可以選擇繼續不交易，保持"持股狀態"，或者選擇賣掉之後變成"冷凍狀態"；
- 當前是"冷凍狀態"，只能選擇繼續不交易，變成"不持股狀態"；
- 當前是"不持股狀態"，可以選擇繼續不交易，保持"不持股狀態"，或者選擇買股票之後變成"持股狀態"；
我增加了最後終止條件：如果是最後一天，並且手上持有股票的話，必須賣出，這樣可以保證最終利益最大。
接下來看看程式碼：
class Solution { int max = 0; public int maxProfit(int[] prices) { if (prices.length == 0) { return 0; } recursiveBuy(-1, false, 0, 0, prices); return max; } public void recursiveBuy( int prePrice, boolean cooldown, int profit, int index, int[] prices) { // 如果到了最後一天，並且手上持有股票的話，必須賣掉 if (index == prices.length - 1) { if (prePrice >= 0 && !cooldown) { profit = profit + prices[index]; } max = Math.max(max, profit); return; } // 當前持有股票 if (prePrice >= 0) { // 此時可以選擇不交易，或者賣掉 // 不交易 recursiveBuy(prePrice, cooldown, profit, index + 1, prices); // 賣掉 recursiveBuy(-1, true, profit + prices[index], index + 1, prices); return; } // 當前不持有股票，可以被動不交易、主動不交易、買 // 如果處於冷凍期，只能被動不交易 if (cooldown) { recursiveBuy(prePrice, false, profit, index + 1, prices); return; } // 不交易 recursiveBuy(prePrice, cooldown, profit, index + 1, prices); // 買 recursiveBuy(prices[index], cooldown, profit - prices[index], index + 1, prices); } }
報了超出時間限制，好的，我們想想怎麼優化。
狀態轉移方程
上面暴力解法之所以會超時，因為重複計算了。我一開始的想法是想著記錄中間結果，但越想越複雜，忍不住看了別人的思路，真的是讓我豁然開朗。那就是狀態轉移方程。
之前我上面提到的是所有狀態可以變成哪些狀態，但其實有些地方想的是不清楚的。我們用箭頭連接兩個狀態，箭頭開始的那端表示前一天的狀態，箭頭終止的那端表示當天的狀態，那麼其內容為：
因為買和賣只是兩個操作，我們認為只能在每一天的0點執行，當天的狀態就由0點之後的狀態來表示。
- "冷凍期"狀態只能是昨天剛買了股票，也就是"不持股"狀態轉移過來。
- "不持股"狀態可以由自己，或者昨天是"持股"狀態，今天賣掉，轉移過來。
- "持股"狀態可以由自己，或者昨天是"冷凍期"狀態，今天買了，轉移過來。
你可能會問，如果這樣表示狀態轉移方程的話，那麼第一天可以買入股票就沒法解釋了。那簡單，為了配合這種特殊情況，我們再記錄一個更早一天的不持股狀態，這樣就可以滿足了。
接下來看看程式碼：
class Solution { public int maxProfit(int[] prices) { if (prices.length < 2) { return 0; } // 因為每次只涉及到前一天的三個狀態值，因此只要三個數字記錄即可 /** * 其狀態轉移方程為： * "冷凍期"只能由"不持股"轉換而來。 * "持股"可以由"持股"和"冷凍期"轉換而來。 * "不持股"可以由"不持股"和"持股"轉換而來。 */ // 定義初始情況 // 不持股 int noStock = 0; // 持股 int hasStock = -prices[0]; // 冷凍期 int cooldown = 0; // 上一次的不持股 int beforeNoStock = 0; for (int i = 1; i < prices.length; i++) { // "不持股"可以由"不持股"和"持股"轉換而來。 noStock = Math.max(beforeNoStock, hasStock + prices[i]); // "持股"可以由"持股"和"冷凍期"轉換而來。 hasStock = Math.max(hasStock, cooldown - prices[i]); // "冷凍期"只能由"不持股"轉換而來。 cooldown = beforeNoStock; // 更新一下"上一次的不持股"狀態 beforeNoStock = noStock; } return Math.max(noStock, cooldown); } }
提交OK。
狀態轉移方程繼續優化
其實從上面的分析，你隱約可以察覺到，"冷凍期"就是一種特殊的"不持股"狀態。根據上面的結論，當你想買股票時，要求的是必須連續兩天"不持股"，這點你想通了嗎？可能也正因為這一點，我們在上面的程式碼中才需要記錄"上一次的不持股"狀態。
既然這樣，我們乾脆就簡化為持股狀態和不持股狀態兩種，其狀態轉移方程可以描述為：
持股狀態可以由自己，或者連續兩天為不持股狀態，今天買了股票，轉移而來。不持股狀態可以由自己，或者前一天為持股狀態，今天賣了股票，轉移而來。
因為我們記錄的是每一天狀態所對應的收入，那麼所謂的連續兩天為不持股狀態，就是相當於從兩天前收入不變。
接下來看看程式碼：
class Solution { public int maxProfit(int[] prices) { if (prices.length < 2) { return 0; } // 這次只有兩個狀態，但需要記錄兩天前的不持股收入 // 定義初始情況 // 不持股 int noStock = 0; // 持股 int hasStock = -prices[0]; // 上一次的不持股 int beforeNoStock = 0, temp; for (int i = 1; i < prices.length; i++) { // 記錄一下"兩天前的不持股"收入 temp = noStock; // "不持股"可以由"不持股"和"持股"轉換而來。 noStock = Math.max(noStock, hasStock + prices[i]); // "持股"可以由"持股"和"冷凍期"轉換而來。 hasStock = Math.max(hasStock, beforeNoStock - prices[i]); // 更新一下"上一次的不持股"狀態 beforeNoStock = temp; } // 最大值一定是最後一天不持股的情況 return noStock; } }
提交OK。
總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。狀態轉移應該還是很經典的方法，主要在於是否可以想出所有狀態及其轉化關係。
