【动态规划】股票买卖问题

算法动态规划空间优化

Algorithm

发布日期: 2021-07-03

文章字数: 4.5k

阅读时长: 20 分

阅读次数:

股票问题

股票问题集合

通用情况

股票问题核心：给定一个表示每天股票价格的数组，在不同的因素的决定下可以获得的最大收益，其中因素包括：允许交易的次数，哪些天允许交易，手续费等。
因此根据这个核心可以得到一种股票问题的通用解法。

dp数组的意义

股票问题最通用的情况由三个特征决定：当前的天数 i、允许的最大交易次数 k 以及每天结束时持有的股票数，因此我们设置：

i 表示第i天；
k 表示允许的最大交易次数；
dp[i][k] 表示在第i天结束时，进行k次交易情况下可以获得的最大利益。

第i天可能发生的操作（买入，卖出，休息）。通过计算得出每个操作可以得到的最大收益。由于题目中都有限制条件，规定不能同时进行多次交易，因此如果决定在第 i 天买入，在买入之前必须持有 0 份股票，如果决定在第 i 天卖出，在卖出之前必须恰好持有 1 份股票。因此需要把dp[i][k]再分为两种情况，即：

dp[i][k][0]表示在第i天结束时，进行k次交易情况下，不持有股票的情况下可以获得的最大收益
dp[i][k][1]表示在第i天结束时，进行k次交易情况下，持有股票的情况下可以获得的最大收益

初始状态

第一天如果不持有收益还是0, 如果持有则减去第一天的股票价

dp[0][k][0] = dp[i][0][0] = 0;
dp[0][K][1] = -prices[i];

注意：当k != 1 || k != 0 的时候，上面式子也是成立的。比如发生了k(k >0)次交易但是不持股，虽然这是不可能的，但是设置成0不会影响最优解；比如第一天发生了k(k >1)次交易，这也是不可能的，虽然没有意义，但是不能设置成0（虽然没有很理解这句话）

转移方程

确定转移方程：
所以状态转移方程就可以确定为当天买入，卖出，休息情况下的最大收益：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
- 前一天不持股，今天什么都不做
- 前一天持股，今天卖出股票（不持股），只有买入操作会改变允许的最大交易次数，k不变
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
- 前一天持股，今天什么都不做
- 前一天不持股，今天买入股票（持股），

输出

max(dp[n-1][k][0])

特定问题

情况一：k = 1

对应题目：121. 买卖股票的最佳时机只允许交易一次
输入：[7,1,5,3,6,4]
输出：5
解释：在第2天（股票价格=1）的时候买入，在第5天（股票价格=6）的时候卖出，最大利润=6-1=5 注意利润不能是7-1=6, 因为卖出价格需要大于买入价格;同时，你不能在买入前卖出股票。
思路：只允许交易一次的话，那么问题状态方程为：

dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]) = max(T[i - 1][1][1], -prices[i])

dp[i - 1][0][0] = 0, 所以代码可以简化为二维数组：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        vector<vector<int>> dp(n, vector<int>(2));
		//第一天不持股
        dp[0][0] = 0;	
        //第一天持股
        dp[0][1] = -prices[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], -prices[i]);
        }
        
        return dp[n-1][0] >=0 ? dp[n-1][0] : 0;
    }
};

如果注意到第 i 天的最大收益只和第 i - 1 天的最大收益相关，可以继续做空间优化

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
		//不持股
        int pro0 = 0;	
        //持股
        int pro1= -prices[0];	

        for(int i = 1; i < n; i++)
        {
        	//不持股的状态由前一天不持股或者前一天持股，今天卖出
            pro0 = max(pro0, pro1 + prices[i]);
            //持股的状态由前一天持股或者前一天不持股，今天买入，交易只有一次
            pro1 = max(pro1, -prices[i]);
        }
        
        return pro0 >=0 ? pro0 : 0;
    }
};

情况二：k = 无穷大

对应题目：122. 买卖股票的最佳时机 II可以无限交易
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第3天（股票价格=5）的时候卖出, 这笔交易所能获得利润=5-1=4。随后，在第4天（股票价格=3）的时候买入，在第5天（股票价格=6）的时候卖出, 这笔交易所能获得利润=6-3=3。

思路：如果k为无穷大，k-1和k可以看成是相同的，那么状态转移方程可以表示为：

dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k-1][0] - prices[i]) = max(T[i - 1][k][1], dp[i-1][k][0]-prices[i])

此时和变量k没有关系，代码可以表示为：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        vector<vector<int>> dp(n, vector<int>(2));
		//第一天不持股
        dp[0][0] = 0;	
        //第一天持股
        dp[0][1] = -prices[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][0] - prices[i]);
        }
        
        return dp[n-1][0];
    }
};

第 i 天的最大收益只和第 i - 1 天的最大收益相关，可以继续做空间优化

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
		//不持股
        int pro0 = 0;	
        //持股
        int pro1= -prices[0];	

        for(int i = 1; i < n; i++)
        {
        	//不持股的状态由前一天不持股或者前一天持股，今天卖出
            pro0 = max(pro0, pro1 + prices[i]);
            //持股的状态由前一天持股或者前一天不持股，今天买入
            pro1 = max(pro1, pro0 -prices[i]);
        }
        
        return pro0;
    }
};

情况三：k = 2

对应题目：123. 买卖股票的最佳时机 III只允许交易两次
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第4天（股票价格=0）的时候买入，在第6天（股票价格=3）的时候卖出，这笔交易所能获得利润=3-0=3 。随后，在第7天（股票价格=1）的时候买入，在第8天（股票价格=4）的时候卖出，这笔交易所能获得利润=4-1=3
思路：如果k为2，每天就有4个未知变量，那么状态转移方程可以表示为：

//第i天第一次卖出 = max(i-1天不持股, i-1天的第1次交易完'持股'+卖出收益) 卖出不增加交易次数
dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
//第i天第一次买入 = max(i-1天持股, i-1天的第0次交易完'不持股'-买入) 买入增加交易次数
dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]) = max(dp[i - 1][1][1], -prices[i])
//第i天第二次卖出 = max(i-1天不持股, i-1天第二次交易完'持股'+卖出收益) 卖出不增加交易次数
dp[i][2][0] = max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])
//第i天第二次买入 = max(i-1天持股, i-1天的第一次交易完'不持股'-买入) 买入增加交易次数
dp[i][2][1] = max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])

由此代码可以表示为：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(2)));
		//第一天不持股
        dp[0][0][0] = 0;	
        //第一天第一次持股
        dp[0][1][1] = -prices[0];
        //第一天第二次不持股（无意义可为0）
        dp[0][2][0] = 0;
        //第一次第二次持股（无意义不可为0）
        dp[0][2][1] = -prices[0];

        for(int i = 1; i < n; i++)
        {
        	//第i天第一次卖出 = max(i-1天不持股, i-1天的第1次交易完'持股'+卖出收益) 卖出不增加交易次数
			dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
			//第i天第一次买入 = max(i-1天持股, i-1天的第0次交易完'不持股'-买入) 买入增加交易次数
			dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]) = max(dp[i - 1][1][1], -prices[i])
			//第i天第二次卖出 = max(i-1天不持股, i-1天第二次交易完'持股'+卖出收益) 卖出不增加交易次数
			dp[i][2][0] = max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])
			//第i天第二次买入 = max(i-1天持股, i-1天的第一次交易完'不持股'-买入) 买入增加交易次数
			dp[i][2][1] = max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])
        }
        
        return max(dp[n-1][1][0],dp[n-1][2][0]);
    }
};

依然可以进行空间优化

class Solution {
    public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        
        int profitOne0 = 0;
        int profitOne1 = -prices[0];
        int profitTwo0 = 0;
        int profitTwo1 = -prices[0];

        for (int i = 1; i < n; i++) {
         	profitOne0 = max(profitOne0, profitOne1 + prices[i]);
            profitOne1 = max(profitOne1, -prices[i]);
            profitTwo0 = max(profitTwo0, profitTwo1 + prices[i]);
            profitTwo1 = max(profitTwo1, profitOne0 - prices[i]);
           
        }
        return max(profitTwo0, profitOne0);
    }
};

情况四：k 为任意值

对应题目：188. 买卖股票的最佳时机 IV只允许交易k次
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第1天 (股票价格=2) 的时候买入，在第2天 (股票价格=4) 的时候卖出，这笔交易所能获得利润=4-2=2 。
思路：情况四是最通用的情况，对于每一天需要使用不同的 k 值更新所有的最大收益，对应持有 0 份股票或 1 份股票。如果 k 超过一个临界值，最大收益就不再取决于允许的最大交易次数，而是取决于股票价格数组的长度，因此可以进行优化。那么这个临界值是什么呢？

一个有收益的交易至少需要两天（在前一天买入，在后一天卖出，前提是买入价格低于卖出价格）。如果股票价格数组的长度为 n，则有收益的交易的数量最多为 n / 2（整数除法）。因此 k 的临界值是 n / 2。如果给定的 k 不小于临界值，即 k >= n / 2，则可以将 k 扩展为正无穷，此时问题等价于情况二。
参考大佬的笔记
根据通用情况的状态转移，代码可以表示为：

class Solution {
    public: 
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n == 0) {
            return 0;
        }
        // 特殊判断，因为交易一次需要 2 天，如果 k >= len / 2，相当于没有限制
        // 转换为「力扣」第 122 题
        if (k >= n / 2) {
            return maxProfit2(prices);
        }
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(k + 1, vector<int>(2)));
        // 初始化：
        for (int i = 1; i <= k; i++) {
            dp[0][i][0] = 0;
            dp[0][i][1] = -prices[0];
        }
        
        for (int i = 1; i < n; i++) 
        {
            for (int j = k; j > 0; j--) 
            {
            	//第i天第j次卖出 = max(i-1天不持股, i-1天的第j次交易完'持股'+卖出收益) 卖出不增加交易次数
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                //第i天第j次买入 = max(i-1天持股, i-1天的第j-1次交易完'不持股'-买入) 买入增加交易次数
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[n - 1][k][0];
    }

    int maxProfit2(vector<int>& prices) {
        int n = prices.size();

        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0] = 0;	
        dp[0][1] = -prices[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][0] - prices[i]);
        }
        
        return dp[n-1][0];
    }
};

依旧是空间优化：

class Solution {
    public: 
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n == 0) {
            return 0;
        }
        // 特殊判断，因为交易一次需要 2 天，如果 k >= len / 2，相当于没有限制
        // 转换为「力扣」第 122 题
        if (k >= n / 2) {
            return maxProfit2(prices);
        }
        vector<vector<int>> dp(k + 1, vector<int>(2));
        // 初始化：
        for (int i = 1; i <= k; i++) {
            dp[i][0] = 0;
            dp[i][1] = -prices[0];
        }
        
        for (int i = 1; i < n; i++) 
        {
            for (int j = k; j > 0; j--) 
            {
            	//第i天第j次卖出 = max(i-1天不持股, i-1天的第j次交易完'持股'+卖出收益) 卖出不增加交易次数
                dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]);
                //第i天第j次买入 = max(i-1天持股, i-1天的第j-1次交易完'不持股'-买入) 买入增加交易次数
                dp[j][1] = max(dp[j][1], dp[j - 1][0] - prices[i]);
            }
        }
        return dp[k][0];
    }

    int maxProfit2(vector<int>& prices) {
        int n = prices.size();
		//不持股
        int pro0 = 0;	
        //持股
        int pro1= -prices[0];	

        for(int i = 1; i < n; i++)
        {
        	//不持股的状态由前一天不持股或者前一天持股，今天卖出
            pro0 = max(pro0, pro1 + prices[i]);
            //持股的状态由前一天持股或者前一天不持股，今天买入
            pro1 = max(pro1, pro0 -prices[i]);
        }
        
        return pro0;
    }
};

情况五：k 为正无穷但有冷却时间

对应题目：309. 最佳买卖股票时机含冷冻期卖出股票后，第二天无法买入
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
思路：由于具有相同的 k 值，因此情况五和情况二非常相似，不同之处在于情况五有限制条件，如果在第 i - 1 天卖出了股票，就不能在第 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 - 2][0] - prices[i]);

所以针对此题，我们引入**dp[i][2]**来表示冷冻期(不持股票，且不能进行买入操作)：

//不持股,当天执行卖出操作
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
//持股
dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
//不持股，当天没有进行任何操作
dp[i][2] = max(dp[i - 1][1], dp[i - 2][0] - prices[i]);

代码表示为：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        vector<vector<int>> dp(n, vector<int>(3));
		//第一天不持股
        dp[0][0] = 0;	
        dp[0][2] = 0;
        //第一天持股
        dp[0][1] = -prices[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] - prices[i]);
            //冷冻期的不持股状态
            dp[i][2] = max(dp[i-1][0], dp[i-1][1]);
        }
        
        return max(dp[n-1][0], dp[n-1][2]);
    }
};

当前天只参考了昨天的状态值，采用滚动数组空间优化：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        vector<int> dp(3);
		//第一天不持股
        dp[0] = 0;	
        dp[2] = 0;
        //第一天持股
        dp[1] = -prices[0];	
		
		int pre0 = dp[0];
		int pre2 = dp[2];
        for(int i = 1; i < n; i++)
        {
            dp[0] = max(dp[0], dp[1] + prices[i]);     
            dp[1] = max(dp[1], pre2 - prices[i]);
            dp[2] = max(dp[0], pre0);
            
            pre0 = dp[0];
            pre2 = dp[2];
        }
        
        return max(dp[0], dp[2]);
    }
};

情况六：k 为正无穷但有手续费

对应题目：714. 买卖股票的最佳时机含手续费每次买入或卖出股票之后的收益需要扣除手续费
思路：只需要在买入或卖出操作时扣除一次手续费，状态转移方程：

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i] - fee);

代码可以表示为：

class Solution {
    public:
    int maxProfit(vector<int>& prices, int fee) {
    
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0] = 0;
        dp[0][1] = -prices[0] - fee;
        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][0] - prices[i] - fee);
        }
        return dp[n - 1][0];
    }
}

空间优化：

class Solution {
    public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        
        int pro0 = 0; 
        int pro1 = -prices[0] - fee;
        
        for (int i = 1; i < n; i++) {
            int newPro0 = max(pro0, pro1 + prices[i]);
            int newPro1 = max(pro1, pro0 - prices[i] - fee);
            pro0 = newPro0;
            pro1 = newPro1;
        }
        return pro0;
    }
};

总结

股票问题最通用的情况由三个特征决定：当前的天数 i、允许的最大交易次数 k 以及每天结束时持有的股票数。在每天再设定好状态进行状态转移，便可以解决不同类型的股票问题。

参考

股票问题系列通解

YukinoKyoU

https://yukinokyou.github.io/2021/07/03/algo-stock/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 YukinoKyoU !

算法动态规划空间优化

【C++】C++关键字总结

C++的关键字用法和注意事项总结

2021-07-05 C++

C++ 语法关键字

【C++】基础知识

关于C++的一些基本知识

2021-07-02 C++

C++ 语法

【动态规划】股票买卖问题

股票问题

股票问题集合

通用情况

dp数组的意义

初始状态

转移方程

输出

特定问题

情况一：k = 1

情况二：k = 无穷大

情况三：k = 2

情况四：k 为任意值

情况五：k 为正无穷但有冷却时间

情况六：k 为正无穷但有手续费

总结

参考

你的赏识是我前进的动力