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

#include <tuple>
#include <unordered_map>
#include <vector>
#include <iostream>

using namespace std;

class Solution {
   private:
    long getKey(int i, int bought) {
        return (long)i << 1 | (long)bought;
    }

    // returns tha max amount of money that can be made starting from a certain state
    int dfs(int i, bool bought, vector<int>& prices, unordered_map<long, int>& dp) {
        int n = prices.size();
        if (i >= n) {
            return 0;
        }
        long key = getKey(i, bought);
        if (dp.find(key) != dp.end()) {
            return dp[key];
        }

        int maxAction = 0;

        if(bought){
            maxAction = dfs(i + 2, false, prices, dp) + prices[i];
        }else{
            maxAction = dfs(i + 1, true, prices, dp) - prices[i];
        }
        
        int maxCooldown = dfs(i + 1, bought, prices, dp);
        int maxProfit = max(maxAction, maxCooldown);
        dp[key] = maxProfit;
        // cout << "i: " << i << ", bought:" << bought << ", profit: " << maxProfit << endl;
        return maxProfit;
    }

   public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // using long for combined key
        unordered_map<long, int> dp;
        return dfs(0, false, prices, dp);
    }
};
17100