<p>You are given an array <code>prices</code> where <code>prices[i]</code> is the price of a given stock on the <code>i<sup>th</sup></code> day.</p>

<p>Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:</p>

<ul>
	<li>After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).</li>
</ul>

<p><strong>Note:</strong> You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> prices = [1,2,3,0,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong> transactions = [buy, sell, cooldown, buy, sell]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> prices = [1]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= prices.length &lt;= 5000</code></li>
	<li><code>0 &lt;= prices[i] &lt;= 1000</code></li>
</ul>

// Utility function for hashing pairs in unordered_map
struct hash_pair {
    template <class T1, class T2>
    size_t operator() (const pair<T1, T2>& p) const {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
static int speedup = []() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    return 0;
}();
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // Memoization map: dp[key] = max_profit
        unordered_map<pair<int, bool>, int, hash_pair> dp;

        // Helper function (recursive DFS)
        function<int(int, bool)> dfs = [&](int i, bool buying) -> int {
            // If we've gone beyond the array length, no more profit can be made
            if (i >= prices.size()) {
                return 0;
            }

            // Check if the current state is already computed
            if (dp.find({i, buying}) != dp.end()) {
                return dp[{i, buying}];
            }

            // Cooldown step (skip one day and check the next)
            int cooldown = dfs(i + 1, buying);

            if (buying) {
                // Option to buy: we pay prices[i], then continue in the next state (selling mode)
                int buy = dfs(i + 1, false) - prices[i];
                dp[{i, buying}] = max(buy, cooldown);
            } else {
                // Option to sell: we gain prices[i], and then skip 1 extra day (due to cooldown)
                int sell = dfs(i + 2, true) + prices[i];
                dp[{i, buying}] = max(sell, cooldown);
            }

            return dp[{i, buying}];
        };

        // Start the DFS from day 0 with the option to buy
        return dfs(0, true);
    }
};


18700