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

from functools import lru_cache

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 2 actions: Buy, Sell.
        # 3 states: Own the stock already (o), don't own the stock and cooldown required (c), don't own the stock and no cooldown required -- i.e. can buy (f).
        
        # Goal: Find the best possible answer from here forward given that you are in each state. 
        # Given all future answers, how do you find each of the answers at the current step?
        # o[i] = max(p[i+1]-p[i]+o[i+1], c[i+1])
        # c[i] = f[i+1]
        # f[i] = max(f[i+1], p[i+1]-p[i]+o[i+1])
        p = prices
        def ret_0(func):
            def wrapper(i):
                if i+1==len(p):
                    return 0
                return func(i)
            return wrapper
                
        @lru_cache(None)
        @ret_0
        def f(i):
            return max(f(i+1), p[i+1]-p[i]+o(i+1))
        
        @lru_cache(None)
        @ret_0
        def c(i):
            return f(i+1)

        @lru_cache(None)
        @ret_0
        def o(i):
            return max(p[i+1]-p[i]+o(i+1), c(i+1))
        
        return f(0)
21000