<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:
    def maxProfit(self, prices: List[int]) -> int:
        dp = {}
        leng = len(prices)
        
        def recursion(i, buy, cooldown):
            if i == leng:  # If we have processed all days
                return 0
            
            if (i, buy, cooldown) in dp:
                return dp[(i, buy, cooldown)]
            
            # Cooldown period: skip this day and reset cooldown
            if cooldown:
                dp[(i, buy, cooldown)] = recursion(i + 1, 1, 0)
                return dp[(i, buy, cooldown)]
            
            # If we can buy
            if buy:
                # Either buy the stock or skip the day
                dp[(i, buy, cooldown)] = max(
                    -prices[i] + recursion(i + 1, 0, 0),  # Buy
                    recursion(i + 1, 1, 0)  # Skip
                )
            else:
                # We have stock, either sell it or hold it
                dp[(i, buy, cooldown)] = max(
                    prices[i] + recursion(i + 1, 1, 1),  # Sell and enter cooldown
                    recursion(i + 1, 0, 0)  # Hold the stock
                )
            
            return dp[(i, buy, cooldown)]
        
        # Start recursion: day 0, can buy, and not in cooldown
        return recursion(0, 1, 0)

18800