力扣 | 动态规划 | 状态机 | 买卖股票 | 买卖股票的最佳时机

文章目录

• 一、309. 买卖股票的最佳时机含冷冻期
• 二、714. 买卖股票的最佳时机含手续费
• 三、123. 买卖股票的最佳时机 III
• 四、188. 买卖股票的最佳时机 IV

本质上这种属于动态规划题目但又有多种状态的，我们只需要正确定义出状态即可。可能每个人定义的状态不一样，但只要是对的就行。

一、309. 买卖股票的最佳时机含冷冻期

LeetCode：309. 买卖股票的最佳时机含冷冻期

个人思路分析：

这个题还蛮不容易的其实，线性dp直接做一维肯定不行，因为对于任何一个股票价格它的状态太多了，不知道何时是买入，不知道有没有买入，你怎么定义dp都无法很好的转移。 那么我们能做的就是给每个价格一个状态，我们分析一下都有哪些状态呢？

• 本次是买入：dp[i][0]
• 本次是卖出：dp[i][1]
• 已经有买入，本次不卖不买：dp[i][2]
• 没有买入，本次不卖不买：dp[i][3]

一共三个状态，我们尝试使用 d p [ i ] [ 0 ] dp[i][0] dp[i][0] ~ d p [ i ] [ 3 ] dp[i][3] dp[i][3] 来表示这三个状态，他们的转移方程为：

• dp[i][0] = dp[i - 1][3] - prices[i]（前一天不能卖出，也不能已经买入过了）
• dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + prices[i]
• dp[i][2] = max(dp[i - 1][2], dp[i - 1][0])
• dp[i][3] = max(dp[i - 1][3], dp[i - 1][1])

时间复杂度： O ( n ) O(n) O(n)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 1) return 0;
        vector<vector<int>> dp(n, vector<int>(4, 0));//dp[i][0]表示买入第i个、dp[i][1]表示卖出的最大受益
        dp[1][0] = -prices[1];
        dp[1][1] = prices[1] - prices[0];
        dp[1][2] = -prices[0];
        dp[1][3] = 0;

        for(int i = 2; i < n; ++ i){
            dp[i][0] = dp[i - 1][3] - prices[i];//（前一天不能卖出，也不能已经买入过了）
            dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + prices[i];
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][0]);
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][1]);
        }
        return max(dp[n - 1][1], dp[n - 1][3]);
    }
};

当然使用滚动数组也是可以优化空间的，这里不做过多解释。

官解思路的本质：

如果说，纯个人思考的思路是：我今天干什么，转移的思路是怎么样我今天才能这样干
那么官解的思路是：今天操作后的状态的是什么，转移的思路是怎么样我今天之后是这样一个状态

官解状态，实际上去思考今天后的状态可能是哪些：

• 手里有股票
• 手里没股票
  • 冷冻期
  • 非冷冻期

其实知道状态后就很容易做了，不过你要怎么去思考完全看你自己如何定义状态，你可以定义今天过后，也可以定义今天干什么，无论如何都要把今天的影响代入，只要状态足以解决问题就够了。

二、714. 买卖股票的最佳时机含手续费

LeetCode：714. 买卖股票的最佳时机含手续费

这个题和之前那个题不同之处在于，这里没有冷冻时间，那么相应的状态也会发生变化。

如果考虑今天之后的状态，则状态可以是：

• 持有股票
• 不持有股票

一共两种状态。

如果考虑今天做什么，则状态可以是：

• 买股票
• 卖出股票
• 持有股票，但什么都不做
• 不持有股票，但什么都不做

一共四种状态。

我们选择今天之后的状态，定义 d p [ i ] [ 0 ] dp[i][0] dp[i][0] ~ d p [ i ] [ 1 ] dp[i][1] dp[i][1]，则有状态转移：

• dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])（持有股票）
• dp[i][1] = max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1])

时间复杂度： O ( n ) O(n) O(n)
可降低空间复杂度为： O ( 1 ) O(1) O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        vector<array<int, 2>> dp((int) prices.size(), array<int, 2>{});
        dp[0][0] = -prices[0], dp[0][1] = 0; 
        
        for(int i = 1; i < (int) prices.size(); ++ i){
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
        }

        return dp[(int) prices.size() - 1][1];
    }
};

本题还能用贪心解决，在股票低谷买入，股票高峰卖出，且保证不亏的时候才进行这个操作。实际上就是摆动序列，在下坡或上坡的时候的差值之和 才能达到 股票高峰 和 股票低谷的差值，所以我们只需要考虑高峰低谷点即可。

三、123. 买卖股票的最佳时机 III

LeetCode：123. 买卖股票的最佳时机 III

本题不能直接用贪心，因此这不是无限次购买，只能买两次，因此如果每次都贪，会导致局部最优不是全局最优。

那么做出这道题实际上，我们只需要理解状态机本质就可以。

可以定义今天之后的状态：

• 持有一张股票，未进行过买卖
• 持有一张股票，进行过一次买卖
• 不持有股票，进行过一次买卖
• 不持有股票，进行过两次买卖
• 不持有股票，未进行过买卖 （直接将这个状态的值写为0即可）

状态可以定义为 d p [ i ] [ 0 ] dp[i][0] dp[i][0] ~ d p [ i ] [ 4 ] dp[i][4] dp[i][4] ，转移方程为：

• dp[i][0] = max(dp[i - 1][0], 0 - prices[i])
• dp[i][1] = max(dp[i - 1][1], dp[i - 1][2] - prices[i])
• dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] + prices[i])
• dp[i][3] = max(dp[i - 1][3], dp[i - 1][1] + prices[i])

对于第0天的情况，如果你认为可以当天买入且卖出，那么dp[0][2] = dp[0][3] = 0;；如果你认为这种情况不存在，那么令这两个的受益为负无穷，即这种情况不予考虑。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<array<int, 4>> dp(n, array<int, 4>{});

        dp[0][0] = -prices[0], dp[0][1] = -0x3f3f3f3f;
        dp[0][2] = -0x3f3f3f3f, dp[0][3] = -0x3f3f3f3f;

        for(int i = 1; i < n; ++ i){
        	dp[i][0] = max(dp[i - 1][0], - prices[i]);
        	dp[i][1] = max(dp[i - 1][1], dp[i - 1][2] - prices[i]);
        	dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] + prices[i]);
        	dp[i][3] = max(dp[i - 1][3], dp[i - 1][1] + prices[i]);
        }

        return max(0, max(dp[n - 1][2], dp[n - 1][3]));
    }
};

同上，空间优化就不做了。

四、188. 买卖股票的最佳时机 IV

LeetCode：188. 买卖股票的最佳时机 IV

这个题通过状态机转换可以知道，如果我们定义多个状态实际上就能解决。

• 定义 d p [ i ] [ 0 ] dp[i][0] dp[i][0]表示今天之后持有一张股票，未进行过买卖
• 定义 d p [ i ] [ 1 ] dp[i][1] dp[i][1]表示今天之后不持有股票，进行过一次买卖
• 定义 d p [ i ] [ 2 ] dp[i][2] dp[i][2]表示今天之后持有一张股票，进行过一次买卖
• 定义 d p [ i ] [ 3 ] dp[i][3] dp[i][3]表示今天之后不持有股票，进行过两次买卖
• ···

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

        vector<vector<int>> dp(n, vector<int>(2 * k, -0x3f3f3f3f));
        dp[0][0] = -prices[0];

        for(int i = 1; i < n; ++ i){
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            for(int j = 1; j < 2 * k; ++ j){
                if(j % 2 == 1){
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                }else{
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                }
            }
        }

        return max(0, *max_element(dp[n - 1].begin(), dp[n - 1].end()));
    }
};

内存优化一下吧，非常简单

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        int m = 2 * k;
        vector<int> dp(m, -0x3f3f3f3f);
        dp[0] = -prices[0];

        for(int i = 1; i < n; ++ i){
            dp[0] = max(dp[0], -prices[i]);
            for(int j = 1; j < m; ++ j){
                if(j % 2 == 1){
                    dp[j] = max(dp[j], dp[j - 1] + prices[i]);
                }else{
                    dp[j] = max(dp[j], dp[j - 1] - prices[i]);
                }
            }
        }

        return max(0, *max_element(dp.begin(), dp.end()));
    }
};