1回答

liuyubobobo

2019-06-28

已采纳

递归 & 记忆化搜索：

https://github.com/liuyubobobo/Play-Leetcode/blob/master/0309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown/cpp-0309/main.cpp

如果不加记忆化搜索会TLE，可以试试看：）

动态规划：

https://github.com/liuyubobobo/Play-Leetcode/blob/master/0309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown/cpp-0309/main2.cpp

==========

buy[i] 表示的是截止到i时间点，最后一个操作是购买，剩余的钱。注意，是最后一个操作是购买，不一定在i这个节点购买；

sell[i] 表示的是截止到i时间点，最后一个操作是卖出，剩余的钱。注意，是最后一个操作是卖出，不一定在i这个节点卖出；

转移方程：

sell[i] = max(sell[i-1], buy[i-1] + prices[i]);    

在i节点，或者和sell[i - 1]一致，即在i节点不卖；

或者在i节点卖出，这就需要看buy[i - 1]的钱，加上在i节点卖出得到的钱prices[i]，二者取最大值；

buy[i] = max(buy[i-1], sell[i-2] - prices[i]);    

在i节点，或者和buy[i - 1]一致，即在i节点不买；

或者在i节点购买，这就需要看sell[i - 2]的钱，因为不能连续购买；减去在i节点购买花费的钱prices[i]，二者取最大值；

继续加油！：）

0

4

pfco

回复

liuyubobobo

好的，谢谢老师

2019-06-28

共4条回复