您现在的位置是：首页 >技术交流 >【Day36 LeetCode】动态规划DP Ⅸ 股票问题网站首页技术交流

一、动态规划DP Ⅸ 股票问题

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

这题在买卖股票的最佳时机Ⅲ的基础上交易次数由2次变成了k次，只是每天的股票状态变多了而已，只要搞清楚有什么状态以及状态之间如何转移就很容易解决。思路几乎和交易两次差不多，代码如下：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<int> dp(2 * k);
        // 初始化
        for(int i=0; i<k; ++i)
            dp[2*i] = -prices[0];
        for(int i=1; i<prices.size(); ++i){
            dp[0] = max(dp[0], -prices[i]);
            dp[1] = max(dp[1], dp[0] + prices[i]);
            for(int j=1; j<k; ++j){
                dp[2*j] = max(dp[2*j], dp[2*j-1]-prices[i]);
                dp[2*j+1] = max(dp[2*j+1], dp[2*j]+prices[i]);
            }
        }
        return dp[2*k-1];
    }
};

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

这题卖出股票完后会有一天的冷冻期不能进行买入股票，这使得每天的股票状态变得复杂。我们需要理清状态，一共有四个状态：a、持有股票状态（不管是今天买入，还是保持之前的持有状态）；非持有股票状态有两种：b、保持非持有状态（之前卖出过股票，经历过冷冻期）；c、今天卖出股票；d、冷冻期
状态转移关系如下图所示（出处：代码随想录）

清楚状态及其转移关系后，就很容易写出相应的代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
       int n = prices.size();
        // 四个状态：持有股票、保持卖出股票、今天卖出股票、冷静期
        vector<int> dp(4);
        dp[0] = -prices[0];
        for(int i=1; i<n; ++i){
            int tmp = dp[0];
            dp[0] = max(dp[0], max(dp[1] - prices[i], dp[3] - prices[i]));
            dp[1] = max(dp[1], dp[3]);
            dp[3] = dp[2];
            dp[2] = tmp + prices[i];
        }
        return max(dp[1], max(dp[2], dp[3]));
    }
};

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

这题只是在买卖股票的最佳时机Ⅱ的基础上给每笔交易的利润需要额外扣除手续费，代码几乎一模一样，只是在计算利润时减去fee。代码如下：

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

二、写在后面

这两天介绍了六道股票问题，分别是 只能交易一次、交易无数次、交易2次/k次、给交易加上冷冻期以及交易需要手续费。只要搞懂了一题的DP代码，即明白股票问题就是要明确当天股票的状态（持有/非持有、一支/n支股票），以及各个状态之间的转移关系，股票问题就迎刃而解了。