Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間3年前 (2022/12/23 16:06)推噓4(4推 0噓 0→)

留言4則, 4人參與討論串149/719 (看更多)

※ 引述《pandix (麵包屌)》之銘言： : 309. Best Time to Buy and Sell Stock with Cooldown : 給你股票每天的價錢，每天能買/賣/不動，問你最大收益是多少 : 手上只能拿一份股票，也就是買完不能再買，要等到賣掉才能執行下一次購買 : 賣完的隔天只能執行不動這個選項 : Example 1: : Input: prices = [1,2,3,0,2] : Output: 3 : Explanation: transactions = [buy, sell, cooldown, buy, sell] : Example 2: : Input: prices = [1] : Output: 0 方法一動態規劃思路： 1.我們可以把股票每天結算的狀態分成三種：當天結束時持有股票當天結束時不持有股票當天的前一天是股票冷卻期因為有三種狀態所以我們需要一個大小為 [n][3] 的陣列。（對於買入股票的收益表示為-prices[i]） 2.每個狀態的狀態轉移方程如下： * 當日結束時持有股票用 dp[i][0] 表示可能是「前日持有股票且今天不買不賣」或「前日不持有股票且未冷卻，今天買入」兩者較大值，表示如下： max(dp[i - 1][0], dp[i - 1][2] - prices[i] * 當日結束時不持有股票用 dp[i][1] 表示可能是「前日不持有股票且今天不買不賣」或「前日持有股票今天賣掉」兩者較大值 dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]) * 當天的前一天是股票冷卻期的最大收益用 dp[i][2] 表示可能是「前日也是冷卻今天不買不賣」或「前日賣了股票的最大收益」兩者較大值 dp[i][2] = max(dp[i - 1][2], dp[i - 1][1]) 3.根據上面的狀態轉移，我們初始化 dp[0][0]（第一天收益）並完成 dp 的表格。 4.返回dp[n - 1][0]（因為手中不留股票的時必定比留股票的收益還高） Java Code： ------------------------------------------ class Solution { public int maxProfit(int[] prices) { int n = prices.length; if (n < 2) { return 0; } int[][] dp = new int[n][3]; dp[0][0] = -prices[0]; for (int i = 1; i < n; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]); dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]); dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1]); } return dp[n - 1][1]; } } ------------------------------------------ 5. 以上的代碼可以進一步優化，觀察之後我們會發現 dp[i][2]（冷卻期）實際上只可能等於 dp[i - 1][1]，因為只有前一天不持有股票(賣出股票)才可能進入冷卻關係式如下： dp[i][2] = dp[i - 2][1]; //所有用到dp[i][2]的地方都替代之要得到冷卻期的最大收益我們需要第i-2天的最大收益，避免越界我們初始化d p到第1天將程式碼改寫如下： Java Code： ------------------------------------------ class Solution { public int maxProfit(int[] prices) { int n = prices.length; if (n < 2) { return 0; } int[][] dp = new int[n][2]; dp[0][0] = -prices[0]; dp[1][0] = Math.max(-prices[0], -prices[1]); dp[1][1] = Math.max(0, -prices[0] + prices[1]); for (int i = 2; i < n; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 2][1] - prices[i]); dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]); } return dp[n - 1][1]; } } ------------------------------------------ 空間複雜度 O(3n) => O(2n) 方法二貪婪演算法思路： 1.根據上面改良版的dp思路，我們實際上每次計算不需要知道dp[i]到dp[n]的所有結果，只會需要前兩個結果所以我們可以把dp矩陣改成變數來儲存，看起來跟對收益做貪婪演算法有90%像。 Java Code： ------------------------------------------ class Solution { public int maxProfit(int[] prices) { int buy = Integer.MIN_VALUE; int preBuy = 0; int sell = 0; int preSell = 0; for (int price : prices) { preBuy = buy; buy = Math.max(preBuy, preSell - price); // 找出最低買價 preSell = sell; sell = Math.max(preSell, preBuy + price); // 找出最高收益 } return sell; } } ------------------------------------------ 對阿 -- https://i.imgur.com/sjdGOE3.jpg