【問(wèn)題描述】[中等]

【解答思路】

1. 動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃流程
第 1 步：設(shè)計(jì)狀態(tài)
f[i]表示第 i 天結(jié)束之后的「累計(jì)最大收益」

第 2 步：狀態(tài)轉(zhuǎn)移方程

f[i][0]=max(f[i?1][0],f[i?1][2]?prices[i])
f[i][1]=f[i?1][0]+prices[i]
f[i][2]=max(f[i?1][1],f[i?1][2])

第 3 步：考慮初始化

第 4 步：考慮輸出
max(f[n?1][0],f[n?1][1],f[n?1][2]) ? max(f[n?1][1],f[n?1][2])

第 5 步：考慮是否可以狀態(tài)壓縮
可 見(jiàn)方法2

f[0][1] 置為0

因?yàn)閒[1][1]只和f[0][0]有關(guān)系，f[0][1]只影響f[1][2],而f[1][2]又是由f[0][1]和f[0][2]共同決定的，第0天f[0][1]和f[0][2]是同一狀態(tài)也就無(wú)所謂了。

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(N)

class Solution {public int maxProfit(int[] prices) {if (prices.length == 0) {return 0;}int n = prices.length;// f[i][0]: 手上持有股票的最大收益// f[i][1]: 手上不持有股票，并且處于冷凍期中的累計(jì)最大收益// f[i][2]: 手上不持有股票，并且不在冷凍期中的累計(jì)最大收益int[][] f = new int[n][3];f[0][0] = -prices[0];for (int i = 1; i < n; ++i) {f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);f[i][1] = f[i - 1][0] + prices[i];f[i][2] = Math.max(f[i - 1][1], f[i - 1][2]);}return Math.max(f[n - 1][1], f[n - 1][2]);} }

2. 動(dòng)態(tài)規(guī)劃路徑壓縮

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

class Solution {public int maxProfit(int[] prices) {if (prices.length == 0) {return 0;}int n = prices.length;int f0 = -prices[0];int f1 = 0;int f2 = 0;for (int i = 1; i < n; ++i) {int newf0 = Math.max(f0, f2 - prices[i]);int newf1 = f0 + prices[i];int newf2 = Math.max(f1, f2);f0 = newf0;f1 = newf1;f2 = newf2;}return Math.max(f1, f2);} }

【總結(jié)】

1.動(dòng)態(tài)規(guī)劃流程

第 1 步：設(shè)計(jì)狀態(tài)
第 2 步：狀態(tài)轉(zhuǎn)移方程
第 3 步：考慮初始化
第 4 步：考慮輸出
第 5 步：考慮是否可以狀態(tài)壓縮

2. 三個(gè)狀態(tài) 三數(shù)組DP 兩數(shù)組DP信息量過(guò)大 處理不來(lái)

轉(zhuǎn)載鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/zui-jia-mai-mai-gu-piao-shi-ji-han-leng-dong-qi-4/

總結(jié)

以上是生活随笔為你收集整理的[Leetcode][第309题][JAVA][最佳买卖股票时机含冷冻期][动态规划][压缩空间]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。