<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:
        # on each day you either buy if you've previously sold
        # or sell if you've previously bought
        # or do nothing (cooldown)
        # permutate all possibilities, remember cache idx, (buy/sell)

        cache = {}
        def dfs(idx, isBuy):
            if idx >= len(prices):
                return 0
            if (idx, isBuy) in cache:
                return cache[(idx, isBuy)]

            _max = -math.inf
            if isBuy: # you've previously bought so you can sell
                _max = max(dfs(idx + 2, not isBuy) + prices[idx], _max)
            if not isBuy: # you've previously sold so you can buy
                _max = max(dfs(idx + 1, not isBuy) - prices[idx], _max)
            # cooldown
            _max = max(dfs(idx + 1, isBuy), _max)
            cache[(idx, isBuy)] = _max
            return cache[(idx, isBuy)]

        return dfs(0, False)



            


17800