给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​

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

你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

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

解题思路

前言:不要关注冷冻期!不要关注冷冻期!不要关注冷冻期!
只关注卖出的那一天!只关注卖出的那一天!只关注卖出的那一天!
题目中定义的“冷冻期”=卖出的那一天的后一天,题目设置冷冻期的意思是,如果昨天卖出了,今天不可买入,那么关键在于哪一天卖出,只要在今天想买入的时候判断一下前一天是不是刚卖出,即可,所以关键的一天其实是卖出的那一天,而不是卖出的后一天

正文:
因为当天卖出股票实际上也是属于“不持有”的状态,那么第i天如果不持有,那这个“不持有”就有了两种状态:1.本来就不持有,指不是因为当天卖出了才不持有的;2.第i天因为卖出了股票才变得不持有

而持有股票依旧只有一种状态

所以对于每一天i,都有可能是三种状态:
0.不持股且当天没卖出,定义其最大收益dpi;
1.持股,定义其最大收益dpi;
2.不持股且当天卖出了,定义其最大收益dpi;

初始化:
dp0=0;//本来就不持有,啥也没干
dp0=-1*prices[0];//第0天只买入
dp0=0;//可以理解成第0天买入又卖出,那么第0天就是“不持股且当天卖出了”这个状态了,其收益为0,所以初始化为0是合理的

重头戏

一、第i天不持股且没卖出的状态dpi,也就是我没有股票,而且还不是因为我卖了它才没有的,那换句话说是从i-1天到第i天转移时,它压根就没给我股票!所以i-1天一定也是不持有,那就是不持有的两种可能:i-1天不持股且当天没有卖出dpi-1;i-1天不持股但是当天卖出去了dpi-1;
所以: dpi=max(dpi-1,dpi-1)

二、第i天持股dpi,今天我持股,来自两种可能:
1、要么是昨天我就持股,今天继承昨天的,也就是dpi-1,这种可能很好理解;
2、要么:是昨天我不持股,今天我买入的,但前提是昨天我一定没卖!因为如果昨天我卖了,那么今天我不能交易!也就是题目中所谓“冷冻期”的含义,只有昨天是“不持股且当天没卖出”这个状态,我今天才能买入!所以是dpi-1-p[i]
所以: dpi=max(dpi-1,dpi-1-p[i])

三、i天不持股且当天卖出了,这种就简单了,那就是说昨天我一定是持股的,要不然我今天拿什么卖啊,而持股只有一种状态,昨天持股的收益加上今天卖出得到的新收益,就是dpi-1+p[i]啦
所以:dpi=dpi-1+p[i]

总结:最后一天的最大收益有两种可能,而且一定是“不持有”状态下的两种可能,把这两种“不持有”比较一下大小,返回即可

// 思路:
//     考虑有多少种状态,每种状态有哪些选择,或者是做了哪些选择后得到哪种状态。
//     注意:到底是先选择了才有状态,还是先由状态才能选择。这里是先选择了,才有状态

// 状态类型有2种:天数和是否持有。
//     天数:一共为1-n天
//     是否持有:分为持有状态、没持有状态1、没持有状态2。
//         持有状态:选择 无处理 和 买入 都有可能达到该状态
//         没持有状态1:选择 无处理 后达到该状态。
//         没持有状态2:选择 卖出 后达到该状态。注意,卖出后进入一天的冻结期。
//     注意:这里为什么要分两种没持有状态,这是为了便于后续状态转移,如果不区分这两种状态,状态转移没法确定当天是否可以进行买入操作。

// dp表示的含义:
//     dp[i][2] : 第i天为没持有状态2时,此时的最大利润
//     dp[i][1] : 第i天为没持有状态1时,此时的最大利润
//     dp[i][0] : 第i天为持有状态时,此时的最大利润
// 状态转移方程:
//     dp[i][0]: 第i天为持有状态时,此时的最大利润
//         无处理后达到该状态: dp[i][0] = dp[i-1][0] // 第i天没有处理就持有股票,证明上一天也持有
//         买入后达到该状态: dp[i][0] = dp[i-1][1]-prices[n] // 第i天能买入股票,证明上一天没持有股票,且没进行卖出操作
//         所以dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[n]); // 这里思考个问题,两种情况都能到达这个状态的话,那如何选择?为什么是取他们的max?
//     dp[i][1]: 第i天为没持有状态1时,此时的最大利润
//         无处理后达到该状态: dp[i][1] = max(dp[i-1][1], dp[i-1][2]) // 有两种到达该状态的情况,取最大那个
//     dp[i][2]: 第i天为没持有状态2时,此时的最大利润
//         卖出后达到该状态: dp[i][2] = dp[i-1][0]+prices[i]

// 最后max(dp[n-1][1], dp[n-1][2])就是题目所需答案。即第n-1天没持有股票时的最大收益

// test case: 
// [1,2,3,0,2]
// [1,2,-2,0,33,0,2]
// [1,2,3,0,2,3,9,0,2,4]
// [2,1]
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 1)
            return 0;
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0; // 假设默认持有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]);
    }
};
Last modification:August 31st, 2021 at 11:39 am
如果觉得我的文章对你有用,请随意赞赏