LeetCode 309 Best Time to Buy and Sell Stock with Cooldown

Tag: 股票问题 LeetCode Posted on 2022-02-04 20:32:55 Edited on 2022-02-05 16:53:06 Views: 153

题目分析

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

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

动态规划法

分析:

  1. 状态:天数,持有状态。
  2. 行为:买入,卖出,不动。
  3. 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]);
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/