• 309. 买卖股票的最佳时机含冷冻期


    给定一个整数数组prices,其中第  prices[i] 表示第 i 天的股票价格 。​

    设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

    • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

    注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

    示例 1:

    输入: prices = [1,2,3,0,2]
    输出: 3 
    解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

    示例 2:

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

    提示:

    • 1 <= prices.length <= 5000
    • 0 <= prices[i] <= 1000
    1. class Solution {
    2. public:
    3. int maxProfit(vector<int>& prices) {
    4. //总共就包括四个状态。定义四个状态,持有0,保持卖出1,刚卖出2,冷冻期3
    5. //dp[i][j]:第i个的状态为j,股票价格最优为dp[i][j]
    6. vectorint>>dp(prices.size()+1,vector<int>(5));
    7. //持有股票0:1、前一天保持卖出状态。2、前一天为冷冻期。3、前一天为持有状态
    8. //dp[i][0] = max(dp[i-1][1] - prices[i], dp[i-1][3] - prices[i], dp[i-1][0]);
    9. //保持卖出1:1、前一天冷冻期。2、前一天为保持卖出
    10. //dp[i][1] = max(dp[i-1][3], dp[i-1][1]);
    11. //刚卖出2:1、前一天为持有
    12. //dp[i][2] = dp[i-1][0] + prices[i];
    13. //冷冻期3:前一天刚好卖出
    14. //dp[i][3] = dp[i-1][2];
    15. //初始化:
    16. dp[0][0] = -prices[0];
    17. dp[0][1] = 0; // 可带入第1天买入。没有本金,只能为0,如果是其他数字,就说明他又本
    18. dp[0][2] = 0;
    19. dp[0][3] = 0; // 可带入第一天冷冻期,如果合理,只能是在第0天买入又卖出,所以第一天为冷冻期,剩余钱为0;
    20. for(int i = 1;i < prices.size();i++){
    21. dp[i][0] = max(dp[i-1][0], max(dp[i-1][3], dp[i-1][1]) - prices[i]);
    22. dp[i][1] = max(dp[i-1][3], dp[i-1][1]);
    23. dp[i][2] = dp[i-1][0] + prices[i];
    24. dp[i][3] = dp[i-1][2];
    25. }
    26. return max(dp[prices.size()-1][3],max(dp[prices.size()-1][1], dp[prices.size()-1][2]));
    27. }
    28. };

  • 相关阅读:
    【Java】可变参数
    浅谈原型链
    C# 结合 JS 暴改腾讯 IM SDK Demo
    开源项目 - RuoYi-Cloud集成PostgreSQL数据库
    Spring Cloud面试题整理
    php output_buffering 缓存使用
    前端反卷计划-组件库-01-环境搭建
    51单片机学习笔记4 新建工程及点亮LED实战
    Unity中Shader抓取屏幕并实现扭曲效果
    2309C++均为某个类型
  • 原文地址:https://blog.csdn.net/qq_63819197/article/details/134497378