<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>

class Solution {
public:
    int dp[5001][2]; // Memoization table
    
    int solve(int i, int holding, const vector<int>& prices) {
        if (i >= prices.size()) return 0;
        
        if (dp[i][holding] != -1) return dp[i][holding];
        
        int cooldown = solve(i + 1, holding, prices); // Cooldown case (skip)
        
        if (holding) {
            // If holding stock, we can sell it or hold it
            int sell = prices[i] + solve(i + 2, 0, prices); // Sell and cooldown next day
            return dp[i][holding] = max(sell, cooldown);    // Maximize profit
        } else {
            // If not holding stock, we can buy it or skip
            int buy = -prices[i] + solve(i + 1, 1, prices); // Buy and move to next day
            return dp[i][holding] = max(buy, cooldown);     // Maximize profit
        }
    }
    
    int maxProfit(vector<int>& prices) {
        memset(dp, -1, sizeof(dp)); // Initialize the memoization table with -1
        return solve(0, 0, prices); // Start with day 0 and not holding stock
    }
};
14100