【学会动态规划】最佳买卖股票时机含冷冻期（15）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学会动态规划】最佳买卖股票时机含冷冻期（15）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：309. 最佳买卖股票时机含冷冻期 - 力扣（Leetcode）

【学会动态规划】最佳买卖股票时机含冷冻期（15）,学会动态规划,动态规划,算法

这道题很好理解，其实就是买股票的时候多了一个冷冻期。

2. 算法原理

1. 状态表示

因为他有三种情况，所以我们也有三种状态表示：

dp[ i ][ 0 ] 表示第 i 天是 “买入” 状态，此时的最大利润。

dp[ i ][ 1 ] 表示第 i 天是 “可卖出” 状态，此时的最大利润。

dp[ i ][ 2 ] 表示第 i 天是 “冷冻” 状态，此时的最大利润。

2. 状态转移方程

我们一个一个分析状态表示：

首先是买入状态，怎么样让第 i 天进入买入状态？

如果 i - 1 天结束是买入状态（买过股票）那就已经是买入状态，

如果 i - 1 天结束是可交易状态（可以卖股票但没买）那只要这天买入，就可以进入买入状态，

如果 i - 1 天结束是冷冻状态（就是卖出的后一天）这样就不能进入买入状态。

然后是冷冻状态，怎么样让第 i 天进入冷冻状态？

如果 i - 1 天结束是买入状态，那只要这天卖出，就能进入冷冻状态，

如果 i - 1 天结束是可交易状态，那只要这天卖了，也能进入冷冻状态，

如果 i - 1 天结束是冷冻状态，那第 i 天结束不可能是冷冻状态，因为没东西可以卖了。

然后是可交易状态，怎么样让第 i 天进入可交易状态？

如果 i - 1 天结束是买入状态，那就不是可交易状态，而是买入状态。

如果 i - 1 天结束是可交易状态，那也只需要啥都不干就是可交易状态，

如果 i - 1 天结束是冷冻状态，那也只需要啥都不干就是可交易状态。

所以我们根据上面的分析来写状态转移方程：

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]);
    }
};