309. Best Time to Buy and Sell Stock with Cooldown(买卖股票+cooldown）有限状态机

比眉伴天荒 2023-02-15 10:23 17阅读 0赞

假设您有一个数组，第i 个元素是第i天给定股票的价格。  
设计算法以找到最大的利润。您可以按照以下限制完成任意数量的交易（即多次购买一股股票）：  
您可能不会同时进行多项交易（即，必须先出售股票才能再次购买）。  
出售股票后，第二天就不能购买股票。（即冷却1天）  
例：

输入： \[1,2,3,0,2\]  
输出： 3  
说明：交易= \[买，卖，冷却，买，卖\]

思路： 三种状态，买卖冷却。三种状态的转换，可以画出来这个示意图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MTk1NjU2_size_16_color_FFFFFF_t_70]  
来自leetcode  
有限状态机，通过这三种状态，s0是空闲时候，可以再次空闲；s1代表买了之后，买了之后下一步可以闲一下，也可以卖掉两种方式；s2代表卖了之后，后一步就只有冷却。  
所以最后我们就可以求得是 s0和s2的最大值。  
s0\[ i \]=max( s2\[i-1\], s0 \[i-1\] );　　　　s0\[i -1\] 是连续两天都是rest的情况。  
s1\[ i\] =max( s0\[i-1\] -prices, s1\[i-1\]) 　　　　代表可以从s0买一次，也可以闲一次再买，因为s\[i\]还是和s\[i-1\] 一样。  
s2\[i \]=s1\[i-1\] +prices. . 　　　因为没有人会只买然后不卖的。

code

//one and sell one share of the stock multiple times 可连续
    class Solution { 
    public:
        int maxProfit(vector<int>& prices) { 
            //有限状态机，一共三个状态：rest冷冻状态，hold买了股票状态，sold卖了股票状态。
            if(prices.size()<=1)return 0;
            vector<int> s0(prices.size());
            vector<int> s1(prices.size());
            vector<int> s2(prices.size());
             s0[0]=0,s1[0]=-prices[0],s2[0]=INT_MIN;
            //持有的时候，可能为负数
            for(int i=1;i<prices.size(); ++i){ 
               s0[i]=max(s2[i-1], s0[i-1]);
                s1[i]=max(s1[i-1],s0[i-1]-prices[i] );
                s2[i]=s1[i-1]+prices[i];
                          //不会出现有人光买不卖的。 
            }
            return max(s0[prices.size()-1],s2[prices.size()-1] );
        }
    };

优化空间：  
三个状态三个值，进入循环之前先走到 了s1状态，然后从s2开始。

int maxProfit(vector<int>& prices) { 
            if (prices.size() < 2) return 0;
            int s0=0,s1=-prices[0], s2=0;
            for(int i=0;i<prices.size();++i)
            { 	
            //从s1开始的，已经走到了s2了；
            int last_s2=s2;
            s2= s1+prices[i];
            s1=max( s1,s0-prices[i]);			//s1的值可以为上一个s1的，说明这次不买，也可以为这次买了
            s0= (s0,last_s2);			//s0一定是上一次的s2相比。
            }
    		return max(s2,s0);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MTk1NjU2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200605100550681.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MTk1NjU2,size_16,color_FFFFFF,t_70