LeetCode309

Question

老师可不可以给出309号问题的思路还有三种解法（递归，记忆化搜索，动态规划）

Answer 1

liuyubobobo 2019-06-28 08:54:21

递归 & 记忆化搜索：

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]，二者取最大值；

继续加油！：）

• 提问者 pfco #1

  非常感谢！

• 提问者 pfco #2

  老师，可不可以对递归的思想阐述一下，我不太能看懂您的代码

• liuyubobobo 回复 提问者 pfco #3

  我补充在原答案上了：）

点开查看后面1条评论