labuladong

LeetCode

发布日期: 2021-09-11

作者: M

文章字数: 1.8k

阅读时长: 7 分

热度:

labuladong一个方法团灭LEETCODE股票买卖问题用的状态机，也就是三维的dp数组（天数，是否处于持有股票的状态（用0和1表示），已经交易的次数）。根据题意不断改变状态转移方程。
本文采用二维数组，把是否持有股票的状态用不同的dp数组（buy，sell）表示。

解题框架来自2 solutions, 2 states DP solutions, clear explanation!

121. 买卖股票的最佳时机

动态规划：

dp[i]数组的含义：前i天的最大收益
- 当天不卖：dp[i]=dp[i-1]
- 当天卖：dp[i]=prices[i]-minPrice
每到新的一天，就更新从开始到当天为止的最低价格

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        vector<int> dp(prices.size(), 0);
        int minPrice=prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            minPrice=min(minPrice,prices[i]);// 更新最低价
            dp[i]=max(dp[i-1],prices[i]-minPrice);
        }
        return dp.back();
    }
};

以下的题目中，当天结束后可能有持有、不持有（能买，不能卖（因为是冷冻期））的状态。因此用到2~3个dp数组来存储状态

122. 买卖股票的最佳时机 II

动态规划解法

不管这个人当天买还是卖还是不操作，他当天结束后最终只有两种状态：持有股票和不持有股票

vector<int>buy(n,0); buy[i]表示第i天处于持有股票的状态（即：处于买的状态）时的最大收益。第i天持有股票是因为有两种情况：
- 前一天也处于持有状态，今天没任何操作：buy[i-1]
- 前一天处于不持有股票状态，今天买了：sell[i-1]-prices[i]
vector<int>sell(n,0);sell[i]表示第i天处于不持有股票的状态（即：处于卖的状态）时的最大收益。第i天不持有股票是因为有两种情况：
- 前一天也处于不持有状态，今天没任何操作：sell[i-1]
- 前一天处于持有股票状态，今天卖了：buy[i-1]+prices[i]
base case: 第0天时若持有股票（说明买了第0天的股票），则buy[0]（表示第0天持有股票状态的最大收益）为-prices[0]。由于第0天不能卖出股票，因此sell[0]为0 （表示第0天无收益）
最后一天不持有的收益比持有的收益大（不持有说明已经卖掉了，持有说明还没卖掉，所以不持有的收益更大），所以返回sell的最后一个元素

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<int>buy(n,0);
        vector<int>sell(n,0);
        buy[0]=-prices[0];
        for (int i = 1; i < n; ++i) {
            buy[i]=max(buy[i-1],sell[i-1]-prices[i]); // 持有股票状态
            sell[i]=max(sell[i-1],buy[i-1]+prices[i]); // 不持有股票状态
        }
        return sell.back();
    }
};

也可以用贪心方法解决：每天都买卖
Krahets的贪心思路

连续上涨交易日，每天都买卖

p3-p1=(p2-p1)+(p3-p2) :第二天把p1卖掉，把p2买了；第三天把p2卖掉，把p3买了

连续下跌交易日，则不买卖收益最大，即不会亏钱
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            tmp = prices[i] - prices[i - 1]
            if tmp > 0: profit += tmp # 当天的tmp若是正收益，则添加到profit中
        return profit

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

交易次数为2，是188题的特例，为构建通用的框架，我们解决188题

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

交易次数为k

在122题的基础上，本题限制了交易次数，最多允许交易k次。变量有两个，天数和已交易的次数，因此dp数组为二维：

buy[i][j]:第i天持有股票状态时，一共已经交易了j次了以后的最大收益
- 在持有（买）股票时如果用了一次交易次数（需要改变次数j）：buy[i][j]=sell[i-1][j-1]-prices[i]
sell[i][j]:第i天不持有股票状态时，一共已经交易了j次了以后的最大收益
- 在不持有（卖）股票时,则不需要改变次数j （因为在买的时候已经改变过了）：sell[i][j]=buy[i-1][j]+prices[i]
二维数组有n行（因为是n天），k+1列（如k=2，则可以选择0次、1次、2次交易，所以要k+1列才能存下状态）

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        if(n<=1)    return 0; // 只有0或1天时，无法完成完整的一次交易，返回0.
        vector<vector<int>>buy(n,vector<int>(k+1,0));
        vector<vector<int>>sell(n,vector<int>(k+1,0));
        for (int i = 0; i < k+1; ++i) {
            buy[0][i]=-prices[0]; // 第0天若处于持有状态，说明买入了(也可能是买了，又卖了，又买了...因此第一列的值都要初始化)当天的股票，此时收益为-prices[0]
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < k+1; ++j) {
                buy[i][j]=max(buy[i-1][j],sell[i-1][j-1]-prices[i]);
                sell[i][j]=max(sell[i-1][j],buy[i-1][j]+prices[i]);
            }
        }
        return sell[n-1][k];
    }
};

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

添加冷冻期后，每天结束后有三种状态

持有股票：buy[i]。这是因为：
- 前一天持有股票，今天没操作：buy[i]=buy[i-1]
- 前一天处于不持有股票且前一天结束后可以买，今天买了: buy[i]=sell[i-1]-prices[i]
- 取这两种情况的最大值
不持有股票，当天结束后可以买：sell[i]。这是因为：
- 前一天不持有股票且前一天结束后可以买，今天没操作：sell[i]=sell[i-1]
- 前一天不持有股票且前一天结束后不可以买，今天就不是冷冻期了，所以变成可以买的状态：sell[i]=cooldown[i-1]
- 取这两种情况的最大值
不持有股票，当天结束后不可以买：cooldown[i]。这是因为：
- 前一天持有股票，今天卖了：cooldown[i]=buy[i-1]+prices[i]

结果就是不持有股票时的最大值

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<int>buy(n,0);
        vector<int>sell(n,0);
        vector<int>cooldown(n,0);
        buy[0]=-prices[0];
        for (int i = 1; i < n; ++i) {
            buy[i]=max(buy[i-1],sell[i-1]-prices[i]); // 持有股票状态
            sell[i]=max(sell[i-1],cooldown[i-1]); // 不持有股票状态,当天结束后可以买
            cooldown[i]=buy[i-1]+prices[i];// 不持有股票状态,当天结束后不可以买
        }
        return max(sell.back(),cooldown.back());
    }
};

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

在122题的基础上，把买股票时的手续费扣除即可

class Solution {
public:
    int maxProfit(vector<int> &prices, int fee) {
        int n = prices.size();
        vector<int> buy(n, 0);
        vector<int> sell(n, 0);
        buy[0] = -prices[0] - fee;
        for (int i = 1; i < n; ++i) {
            buy[i] = max(buy[i - 1], sell[i - 1] - prices[i] - fee); // 持有股票状态
            sell[i] = max(sell[i - 1], buy[i - 1] + prices[i]); // 不持有股票状态
        }
        return sell.back();
    }
};