309. 买卖股票的最佳时机含冷冻期(leetcode) 动态规划思想-Toy模板网

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

前言

在本文章中，我们将要详细介绍一下Leetcode中买卖股票的最佳时机含冷冻期相关的内容，本题采用动态规划的思想解决

一、题目分析

309. 买卖股票的最佳时机含冷冻期(leetcode) 动态规划思想,刷题,leetcode,动态规划,算法,c++,职场和发展,蓝桥杯

二、算法原理

1.状态表示

列出dp表，dp表中值的含义是什么
dp[i]表示第i天之后此时的最大利润
由于第i天不确定具体状态，多状态dp问题
🌟 .dp[i][0]:手中有股票没有卖出，我们简单称为买入状态，此时的最大利润
🌟 .dp[i][1]:处于冷冻期，无法购买股票，我们称为冷冻期，此时的最大利润
🌟 .dp[i][2]:手中没有股票，也不处于冷冻期，此时的最大利润

2.状态转移方程

根据最近一步划分问题

根据状态表示，我们可以划分为9种不同的转换
🌟 .(i-1)天处于买入状态，第i天处于买入状态:这个是可以的，这一天啥也不干
🌟 .(i-1)天处于买入状态，第i天处于冷冻期状态:这个可以，就是这天把股票卖了，赚了钱，需要加上prices[i]的值（涉及利润）
🌟 .(i-1)天处于买入状态，第i天处于正常状态:这个不可以，你手中有股票，不处于正常状态，即使把股票卖了，也得先经过冷冻期才可以
🌟 .(i-1)天处于冷冻期状态，第i天处于冷冻期状态:这个不可以，冷冻期只能有一天
🌟 .(i-1)天处于冷冻期状态，第i天处于买入状态:这个不可以，冷冻期是不能买股票的
🌟 .(i-1)天处于冷冻期状态，第i天处于正常状态:这个可以，经过一天之后进入正常状态。
🌟 .(i-1)天处于正常状态，第i天处于正常状态:这个可以，感觉这个股票不好，等一等再买
🌟 .(i-1)天处于正常状态，第i天处于买入状态:这个可以，可以进行购买股票，买股票需要花钱，需要减去股票的钱pricesi
🌟 .(i-1)天处于正常状态，第i天处于冷冻期状态:这个不可以，冷冻期是在股票卖了之后才进入的

下面有个简图描述上面信息
309. 买卖股票的最佳时机含冷冻期(leetcode) 动态规划思想,刷题,leetcode,动态规划,算法,c++,职场和发展,蓝桥杯
箭头方向表示：从（i-1）天到第i天

3.初始化+边界条件

本题初始化比较简单，不需要创建虚拟节点了
dp[0][0]=-prices[0]；这一天只买了股票，买是需要花钱的
dp[0][1]=0;买了有紧接着卖了，没有利润
dp[0][2]=0;

4.填表顺序

从左往右

5.返回值是什么

最后一天的最大收益有两种可能，而且一定是“不持有”状态下的两种可能，把这两种“不持有”比较一下大小，返回即可
max(dp[n-1][1],dp[n–1][2]);

三、代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        //建表
        int n=prices.size();
        if(n==0)
        {
            return 0;
        }
        vector<vector<int>>dp (n,vector<int>(3));
        //初始化
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        dp[0][2]=0;
        //填表
        for(int i=1;i<n;i++)
        {
            dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i]);
            dp[i][1]=dp[i-1][0]+prices[i];
            dp[i][2]=max(dp[i-1][2],dp[i-1][1]);
        }
        //返回值
        return max(dp[n-1][1],dp[n-1][2]);
    }
};