【代码随想录】刷题笔记Day50

2024-01-10 11:36:52

前言

  • 昨晚做了好多梦啊......不知道是睡好了还是没睡好,又赖了会床才来工位

309. 买卖股票的最佳时机含冷冻期 - 力扣(LeetCode)

  • dp[i][j]含义:第i天状态为j+1,所剩的最多现金为dp[i][j]
    • 状态一:持有股票状态(今天买 + 之前就买然后没有操作)
    • 状态二:保持卖出股票的状态(两天前就卖出了股票度过一天冷冻期 + 前一天就是卖出股票状态,一直没操作)
    • 状态三:今天卖出股票
    • 状态四:今天为冷冻期状态,但冷冻期状态不可持续,只有一天!
  • 递推公式
    • dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);
    • dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
    • dp[i][2] = dp[i - 1][0] + prices[i];
    • dp[i][3] = dp[i - 1][2];
  • 初始化
    • dp[0][0] = -prices[0],其他为0
  • 结果取状态二,状态三,和状态四的最大值
  • class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int len = prices.size();
            vector<vector<int>> dp(len, vector<int>(4, 0));
            dp[0][0] = -prices[0];
            for(int i = 1; i < len; i++){
                // 状态一持有:原状 + 二买入 +四买入  
                dp[i][0] = max(dp[i-1][0], max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));
                // 状态二保卖:原状 + 四
                dp[i][1] = max(dp[i-1][1], dp[i-1][3]);
                // 状态三今卖:一卖出
                dp[i][2] = dp[i-1][0] + prices[i];
                // 状态四冷冻:今卖
                dp[i][3] = dp[i-1][2];
            }
            return max(dp[len-1][1], max(dp[len-1][2], dp[len-1][3]));
        }
    };
  • 也可以三个状态
  • ?

714. 买卖股票的最佳时机含手续费 - 力扣(LeetCode)?

  • ?类似买卖股票II,只是在卖出的时候计算了手续费,秒了
  • class Solution {
    public:
        int maxProfit(vector<int>& prices, int fee) {
            int len = prices.size();
            vector<vector<int>> dp(len, vector<int>(2, 0));
            dp[0][0] = -prices[0];
            for(int i = 1; i < len; 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][0] + prices[i] - fee);
            }
            return dp[len - 1][1];
        }
    };

股票问题汇总

  • ?

后言

  • 今天刷题就到这里,不确定明天开不开组会,下午学完车赶点活吧~

文章来源:https://blog.csdn.net/qq_56077562/article/details/135495885
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。