?? 算法刷題專欄 | 面試必備算法 | 面試高頻算法 ??
?? 越難的東西,越要努力堅(jiān)持，因?yàn)樗哂泻芨叩膬r(jià)值，算法就是這樣?
?? 作者簡(jiǎn)介：碩風(fēng)和煒，CSDN-Java領(lǐng)域新星創(chuàng)作者??，保研|國(guó)家獎(jiǎng)學(xué)金|高中學(xué)習(xí)JAVA|大學(xué)完善JAVA開發(fā)技術(shù)棧|面試刷題|面經(jīng)八股文|經(jīng)驗(yàn)分享|好用的網(wǎng)站工具分享??????
?? 恭喜你發(fā)現(xiàn)一枚寶藏博主,趕快收入囊中吧??
?? 人生如棋，我愿為卒，行動(dòng)雖慢，可誰(shuí)曾見(jiàn)我后退一步？????

?? 知識(shí)回顧

大家在學(xué)習(xí)這道題目之前，可以先去看一下買賣股票最佳時(shí)機(jī)1，再看這個(gè)題目就更容易理解了。
博客的地址放到這里了，可以先去學(xué)習(xí)一下這到題目。

• 【LeetCode股票買賣系列:121. 買賣股票的最佳時(shí)機(jī) | 一次遍歷 | 暴力遞歸=＞記憶化搜索=＞動(dòng)態(tài)規(guī)劃】
• 【LeetCode股票買賣系列:122. 買賣股票的最佳時(shí)機(jī) II | 貪心 | 暴力遞歸=＞記憶化搜索=＞動(dòng)態(tài)規(guī)劃】
• 【LeetCode股票買賣系列:123. 買賣股票的最佳時(shí)機(jī) III 暴力遞歸=＞記憶化搜索=＞動(dòng)態(tài)規(guī)劃】
• 【LeetCode股票買賣系列:188. 買賣股票的最佳時(shí)機(jī) IV | 暴力遞歸=＞記憶化搜索=＞動(dòng)態(tài)規(guī)劃】

?? 題目鏈接

• 309. 最佳買賣股票時(shí)機(jī)含冷凍期

? 題目描述

給定一個(gè)整數(shù)數(shù)組prices，其中第 prices[i] 表示第 i 天的股票價(jià)格 。?

設(shè)計(jì)一個(gè)算法計(jì)算出最大利潤(rùn)。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:

賣出股票后，你無(wú)法在第二天買入股票 (即冷凍期為 1 天)。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。

示例 1:

輸入: prices = [1,2,3,0,2]
輸出: 3
解釋: 對(duì)應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]
示例 2:

輸入: prices = [1]
輸出: 0

提示：

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

?? 求解思路&實(shí)現(xiàn)代碼&運(yùn)行結(jié)果

? 暴力法

?? 求解思路

1. 首先該題目核心求解思路我們之前也已經(jīng)講過(guò)了，不會(huì)的同學(xué)可以看一下之前的文章內(nèi)容；
2. 我們將這道題目區(qū)別于其它股票題目不同的內(nèi)容標(biāo)記出來(lái)，可以多次買賣 && 賣出股票后，你無(wú)法在第二天買入股票 (即冷凍期為 1 天);
3. 第一個(gè)限制條件我們?cè)趺慈プ?，前面都已?jīng)講過(guò)了，我們著重看一下第二個(gè)限制條件，第二個(gè)條件其實(shí)也比較簡(jiǎn)單，主要就是如果當(dāng)前我們持有股票，并且答案是來(lái)自此時(shí)我們需要買入的時(shí)候，那么此時(shí)答案必須來(lái)自前倆天不持有股票的狀態(tài)。
4. 接下來(lái)我們就來(lái)實(shí)現(xiàn)一下具體的代碼。

?? 實(shí)現(xiàn)代碼

class Solution {

    int[] prices;

    public int maxProfit(int[] prices) {
        this.prices=prices;
        int n=prices.length;
        return process(n-1,0);
    }

    public int process(int i,int flag){
        if(i<0) return flag==1?Integer.MIN_VALUE:0;
        if(flag==1) return Math.max(process(i-1,1),process(i-2,0)-prices[i]);
        return Math.max(process(i-1,0),process(i-1,1)+prices[i]);
    }
}

?? 運(yùn)行結(jié)果

果然不出我們所料，時(shí)間超限了，不要緊張，我們來(lái)繼續(xù)優(yōu)化它！

? 記憶化搜索

?? 求解思路

1. 因?yàn)樵谶f歸的過(guò)程中，會(huì)重復(fù)的出現(xiàn)一些多次計(jì)算的結(jié)果，我們通過(guò)開辟一個(gè)數(shù)組，將結(jié)果提前緩存下來(lái)，算過(guò)的直接返回，避免重復(fù)計(jì)算，通過(guò)空間來(lái)去換我們的時(shí)間。

?? 實(shí)現(xiàn)代碼

class Solution {
    int[] prices;
    int[][] dp;
    public int maxProfit(int[] prices) {
        this.prices=prices;
        int n=prices.length;
        dp=new int[n][2];
        for(int i=0;i<n;i++) Arrays.fill(dp[i],-1);
        return process(n-1,0);
    }

    public int process(int i,int flag){
        if(i<0) return flag==1?Integer.MIN_VALUE:0;
        if(dp[i][flag]!=-1) return dp[i][flag];
        if(flag==1) return dp[i][flag]=Math.max(process(i-1,1),process(i-2,0)-prices[i]);
        return dp[i][flag]=Math.max(process(i-1,0),process(i-1,1)+prices[i]);
    }
}

?? 運(yùn)行結(jié)果

加一個(gè)緩存表，通過(guò)?。。?br>

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

?? 求解思路

1. 有了遞歸，有了記憶化搜索，接下來(lái)就是動(dòng)態(tài)規(guī)劃了，直接上手。

?? 實(shí)現(xiàn)代碼

class Solution {
    int[] prices;
    int[][] dp;
    public int maxProfit(int[] prices) {
        this.prices=prices;
        int n=prices.length;
        dp=new int[n][2];
        dp[0][1]=-prices[0];
        dp[0][0]=0;
        if(n>1){
            dp[1][1]=Math.max(dp[0][1],-prices[1]);
            dp[1][0]=Math.max(dp[0][0],dp[0][1]+prices[1]);
        }
        for(int i=2;i<n;i++){
            dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i]);
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
        }
        return dp[n-1][0];
    }
}

?? 運(yùn)行結(jié)果

搞定,簡(jiǎn)直不要太爽！

?? 共勉

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-432483.html

到了這里，關(guān)于【LeetCode股票買賣系列:309. 最佳買賣股票時(shí)機(jī)含冷凍期 | 暴力遞歸=＞記憶化搜索=＞動(dòng)態(tài)規(guī)劃】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！