LeetCode 309 Best Time to Buy and Sell Stock with Cooldown

    
        标签：
        
            股票问题
        
            LeetCode
        
    发布于：2022-02-04 20:32:55
    编辑于：2022-02-05 16:53:06
    浏览量：965

题目分析

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

不限制买卖次数，但是卖出后冷却一天。

动态规划法

分析：

状态：天数，持有状态。
行为：买入，卖出，不动。
base case：第零天不能持有，且此时利润为 0。

这里的冷却一天要怎么体现在状态转移方程上呢？

dp[d][1] = max(dp[d-1][1], dp[d-2][0] - prices[d - 1]);

由于这里的索引出现了 d-2，我们必须处理该 case，其实就是要手动给个 0 值。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size() + 1, vector<int>(2, 0));
        dp[0][1] = INT_MIN;
        for (int d = 1; d <= prices.size(); d++) {
            dp[d][0] = max(dp[d-1][0], dp[d-1][1] + prices[d - 1]);
            if (d - 2 == -1) {
                dp[d][1] = max(dp[d-1][1], - prices[d - 1]);
            } else {
                dp[d][1] = max(dp[d-1][1], dp[d-2][0] - prices[d - 1]);
            }
        }
        return dp[prices.size()][0];
    }
};

动态规划法（冷却也作为状态）

注意这里将冷却状态加入到持有状态中，将其扩充为：持有，售出冷却中，冷却完毕。

那 base case 有：day 0 时不能为持有状态和售出冷却中状态。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size() + 1, vector<int>(3, 0));
        // 0 means holding, 1 means empty stock (able to buy again), 2 means empty stock (cooling down)
        dp[0][0] = INT_MIN;
        dp[0][2] = INT_MIN;
        for (int d = 1; d <= prices.size(); d++) {
            dp[d][0] = max(dp[d-1][0], dp[d-1][1] - prices[d - 1]);
            dp[d][1] = max(dp[d-1][1], dp[d-1][2]);
            dp[d][2] = dp[d-1][0] + prices[d - 1];
        }
        return max(dp[prices.size()][1], dp[prices.size()][2]);
    }
};

Links: leetcode-309-best-time-to-buy-and-sell-stock-with-cooldown