一起学习交流~

最佳买卖股票时机含冷冻期-dp三种情况

算法 laomuji 8个月前 (02-05) 316次浏览 已收录 0个评论

目录

题目

给定一个整数数组prices,其中第  prices[i] 表示第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

class Solution {
/*
当天有三种状态
持有股票 dpA
未持有股票(没有卖股票,明天不处于冻结期) dpB
未持有股票(今天卖出股票,明天处于冻结期) dpC

持有股票
分为两种情况
1.昨天持有的 dpA[i-1]
2.昨天没有持有(今天不能处于冻结期,所以依赖于dpB) dpB[i-1]-prices[i]
dpA[i]=max(dpA[i-1],dpB[i-1]-prices[i])

未持有股票(没有卖股票,明天不处于冻结期)
没持有股票,那么只可能是dpB和dpC其中之一
也就是 今天不处于冻结期或者今天处于冻结期
dpB[i]=max(dpB[i-1],dpC[i-1])

未持有股票(今天卖出股票,明天处于冻结期)
今天卖出股票的收益 是 昨天持有股票的收益+今天卖出股票的收益
dpC[i]=dpA[i-1]+prices[i]

*/
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        vector<int>dpA(size);
        vector<int>dpB(size);
        vector<int>dpC(size);
        dpA[0]=0-prices[0];
        for(int i =1;i<size;i++){
            dpA[i]=max(dpA[i-1],dpB[i-1]-prices[i]);
            dpB[i]=max(dpB[i-1],dpC[i-1]);
            dpC[i]=dpA[i-1]+prices[i];
        }
        return max(dpB[size-1],dpC[size-1]);
    }
};
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论