309. Best Time to Buy and Sell Stock with Cooldown
follow up of 714. Best Time to Buy and Sell Stock with Transaction Fee and 188. Best Time to Buy and Sell Stock IV.
Memoization
```cpp
class Solution {
public:
vector<vector> dp;
vector prices;
int fun(int i, int bought) {
if (i >= prices.size()) {
return 0;
}
int &ans = dp[i][bought];
if (ans == -1) {
int doNothing = fun(i + 1, bought);
int doSomeThing;
if (bought)
doSomeThing = fun(i + 2, !bought) + prices[i];
else
doSomeThing = fun(i + 1, !bought) - prices[i];
ans = max(doNothing, doSomeThing);
}
return ans;
}
int maxProfit(vector& prices) {
dp.resize(prices.size() + 1, vector(2, -1));
this->prices = prices;
return fun(0, 0);
}
};
```
</details>
Iterative
```cpp
class Solution {
public:
int maxProfit(vector& prices) {
vector<vector> dp;
dp.resize(prices.size() + 2, vector(2, 0));
for (int i = prices.size() - 1; i >= 0; i--) {
for (int bought = 1; bought >= 0; bought --) {
dp[i][bought] = dp[i + 1][bought];
dp[i][bought] = max(dp[i][bought],
bought
? dp[i + 2][!bought] + prices[i]
: dp[i + 1][!bought] - prices[i]);
}
}
return dp[0][0];
}
};
```
</details>