309. Лучшее время для покупки и продажи акций с охлаждением (Best Time to Buy and Sell Stock with Cooldown)

Задание.

Вам предоставляется массив prices (цен), где prices[i] – это цена данной акции на i-й день.

Найдите максимальную прибыль, которой вы можете достичь. Вы можете совершать столько транзакций, сколько захотите (т.е. покупать одну и продавать одну акцию несколько раз) со следующими ограничениями:

• После того, как вы продадите свои акции, вы не сможете купить их на следующий день (т.е. даётся день на охлаждение).

Примечание: Вы не можете участвовать в нескольких транзакциях одновременно (т.е. вы должны продать акции, прежде чем покупать снова).

Пример 1.

Входные данные: prices = [1,2,3,0,2]

Результат: 3

Объяснение: transactions = [buy, sell, cooldown, buy, sell]

Пример 2.

Входные данные: prices = [1]

Результат: 0

Решение.

class Solution {
private:
    int n;
    int solve(vector<int>& prices, int i, int to_buy, vector<vector<int>>& dp) {
        if(i >= n) return 0; // base case

        if(dp[i][to_buy] != INT_MIN) return dp[i][to_buy];

        int curr_price = prices[i];
        int ans;

        if(to_buy == 1) { 
            int buy_curr = solve(prices, i+1, 0, dp) - curr_price; // buy on current price
            int buy_next = solve(prices, i+1, 1, dp); // leave current day

            ans = max(buy_curr, buy_next);
        } else {
            int sold_curr = solve(prices, i+2, 1, dp) + curr_price; // sell on current price
            int sold_next = solve(prices, i+1, 0, dp); // sell on next day's price

            ans = max(sold_curr, sold_next);
        }

        return dp[i][to_buy] = ans;
    }
public:
    int maxProfit(vector<int>& prices) {
        n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, INT_MIN)); 

        return solve(prices, 0, 1, dp);
    }
};

Способ решения.

Нужно сделать выбор, и лучший выбор - это ответ.

1. Если вы ничего не купили, то можете либо выбрать текущий товар, либо перейти к следующему.

2. Если вы купили, то либо вы можете продать сегодня, а затем перейти к следующему дню, либо вы можете сделать перерыв и продавать в другие дни.

И если мы построим дерево решений, то сможем увидеть перекрывающиеся подзадачи. Следовательно, мы можем запомнить решение с помощью динамического программирования.

Решение 2 (конечный автомат)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if (len < 2) return 0;
        int s0 = 0, s1 = -prices[0], s2 = 0;
        for (int i = 1; i < len; ++i) {
            int last_s2 = s2;
            s2 = s1 + prices[i];
            s1 = max(s0 - prices[i], s1);
            s0 = max(s0, last_s2);
        }
        return max(s0, s2);
    }
};

Есть три состояния, в зависимости от действия, которое можно предпринять.