目錄

動態(tài)規(guī)劃怎么學？

1. 題目解析

2. 算法原理

1. 狀態(tài)表示

2. 狀態(tài)轉(zhuǎn)移方程

3. 初始化

4. 填表順序

5. 返回值

3. 代碼編寫

寫在最后：

動態(tài)規(guī)劃怎么學？

學習一個算法沒有捷徑，更何況是學習動態(tài)規(guī)劃，

跟我一起刷動態(tài)規(guī)劃算法題，一起學會動態(tài)規(guī)劃！

1. 題目解析

題目鏈接：309. 最佳買賣股票時機含冷凍期 - 力扣（Leetcode）

這道題很好理解，其實就是買股票的時候多了一個冷凍期。?

2. 算法原理

1. 狀態(tài)表示

因為他有三種情況，所以我們也有三種狀態(tài)表示：

dp[ i ][ 0 ] 表示第 i 天是 “買入” 狀態(tài)，此時的最大利潤。

dp[ i ][ 1?] 表示第 i 天是 “可賣出” 狀態(tài)，此時的最大利潤。

dp[ i ][ 2?] 表示第 i 天是 “冷凍” 狀態(tài)，此時的最大利潤。

2. 狀態(tài)轉(zhuǎn)移方程

我們一個一個分析狀態(tài)表示：

首先是買入狀態(tài)，怎么樣讓第 i 天進入買入狀態(tài)？

如果 i - 1 天結(jié)束是買入狀態(tài)（買過股票）那就已經(jīng)是買入狀態(tài)，

如果 i - 1 天結(jié)束是可交易狀態(tài)（可以賣股票但沒買）那只要這天買入，就可以進入買入狀態(tài)，

如果 i - 1 天結(jié)束是冷凍狀態(tài)（就是賣出的后一天）這樣就不能進入買入狀態(tài)。

然后是冷凍狀態(tài)，怎么樣讓第 i 天進入冷凍狀態(tài)？

如果 i - 1 天結(jié)束是買入狀態(tài)，那只要這天賣出，就能進入冷凍狀態(tài)，

如果 i - 1 天結(jié)束是可交易狀態(tài)，那只要這天賣了，也能進入冷凍狀態(tài)，

如果 i - 1 天結(jié)束是冷凍狀態(tài)，那第 i 天結(jié)束不可能是冷凍狀態(tài)，因為沒東西可以賣了。

然后是可交易狀態(tài)，怎么樣讓第 i 天進入可交易狀態(tài)？

如果 i - 1 天結(jié)束是買入狀態(tài)，那就不是可交易狀態(tài)，而是買入狀態(tài)。

如果 i - 1 天結(jié)束是可交易狀態(tài)，那也只需要啥都不干就是可交易狀態(tài)，

如果 i - 1 天結(jié)束是冷凍狀態(tài)，那也只需要啥都不干就是可交易狀態(tài)。

所以我們根據(jù)上面的分析來寫狀態(tài)轉(zhuǎn)移方程：

dp[ i ][ 0 ] = max( dp[ i - 1 ][ 0 ]，dp[ i - 1 ][ 1 ] - p[ i ]?)

dp[ i ][ 1 ] = max(?dp[ i - 1 ][ 1 ]，dp[ i - 1 ][ 2?]?)

dp[ i ][ 2?] =? dp[ i - 1 ][ 0 ] + p[ i ]

3. 初始化

我們只需要把 dp[ 0 ][ 0 ] 初始化成 -p[ 0 ] 即可，因為買入了所以最大利潤就是一個負值。

4. 填表順序

從左往右，依次填寫三個表即可。

5. 返回值

其實就是：max( dp[ n - 1?][ 1 ]，dp[ n - 1 ][ 2 ]?)

第一種買入的情況不考慮，因為都買入了，肯定不會是最大利潤。

3. 代碼編寫

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3));
        dp[0][0] = -prices[0];
        for(int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }
        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};

寫在最后：

以上就是本篇文章的內(nèi)容了，感謝你的閱讀。

如果感到有所收獲的話可以給博主點一個贊哦。

如果文章內(nèi)容有遺漏或者錯誤的地方歡迎私信博主或者在評論區(qū)指出~文章來源地址http://www.zghlxwxcb.cn/news/detail-624147.html

到了這里，關(guān)于【學會動態(tài)規(guī)劃】最佳買賣股票時機含冷凍期（15）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！