<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 = {}  # 使用字典来存储动态规划的结果，key = (i, buying)，val = 最大利润
        def dfs(i, buying):
            if i >= len(prices):
                return 0  # 当超过最后一天时，没有利润可以赚取，返回0
            if (i, buying) in dp:
                return dp[(i, buying)]  # 如果已经计算过这个状态，直接返回缓存结果

            if buying:
                # 选择买入：当前利润 = 下一天卖出后的利润 - 当前价格
                buy = dfs(i + 1, not buying) - prices[i]
                # 选择冷静期：当前利润 = 下一天买入或冷静期后的最大利润
                cooldown = dfs(i + 1, buying)
                # 取买入或冷静期的最大值
                dp[(i, buying)] = max(buy, cooldown)
            else:
                # 选择卖出：当前利润 = 卖出价格 + 冷冻期后的最大利润
                sell = dfs(i + 2, not buying) + prices[i]
                # 选择冷静期：当前利润 = 下一天卖出或冷静期后的最大利润
                cooldown = dfs(i + 1, buying)
                # 取卖出或冷静期的最大值
                dp[(i, buying)] = max(sell, cooldown)
            
            return dp[(i, buying)]  # 返回当前状态的最大利润

        return dfs(0, True)  # 从第0天开始，并且假设我们要买入

17900