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

        # hold -> True, meaning the person is holding a stock on Day N
        # hold -> False meaning the person is not holding a stock on Day N

        @cache
        def dfs(day, hold):
            """
            hold: boolean
            meaning if the person currently holds a stock
            """
            if day < 0:
                if hold:
                    return -inf # why put -inf here? profit = -stockprice[Day-1] + stockprice[DayN]
                elif not hold:
                    return 0

            if hold:
                # current state is hold
                # it can come from
                # day-1 -> hold, and keep holding, state is hold
                # day-2 -> non-hold state, buy stock on day, so that the state is hold
                # there is a cooldown for day-2 to day-1
                return max(dfs(day-1, True), dfs(day-2, False)-prices[day])

            elif not hold:
                # current state is not hold
                # it can come from
                # day-2 -> hold, but sell stock on day, state becomes unhold on day
                # day-1 -> unhold, keep unholding
                return max(dfs(day-1, True)+prices[day], dfs(day-1, False))

        N = len(prices)
        return dfs(N-1, False)




20500