<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 {
public:
// max profit 
// sell a stock cannot buy next day 
// buy at lowest sell at highest greedy won't work 
// profit = (sell - buy)    or   profit - buy   andn profit + buy 
// dp 
// top down with recursion 

    int helper(vector<int>& prices  , int index , int holding ,  vector< vector<int> > & dp) {

        if(index >= prices.size() ) return 0 ; 

        if(dp[index][holding] != -1 ) return dp[index][holding] ; 

    
        int skip = helper(prices , index+1 , holding , dp ) ;

        // buy 
        if(!holding){
            int buy = -prices[index] + helper( prices ,  index + 1  , 1 , dp  ) ; 
            dp[index][holding] = max(buy, skip);
        } 
        // sell 
        else {
            int sell = prices[index] + helper( prices ,  index + 2  , 0 , dp  ) ; //+2 to awkowledge cooldown
            dp[index][holding] = max(sell, skip);    
        } 
         
        return dp[index][holding] ;


    }







    int maxProfit(vector<int>& prices) {

        int n = prices.size() ; 
        vector< vector<int> > dp ( n , vector<int>( 2 , -1 ) )  ; 


        // buy then sell 

        return helper( prices , 0 , 0 , dp ) ; 


        
    }
};
14900