【LeetCode】309. Best Time to Buy and Sell Stock with Cooldown 解题报告（Python & C++）
作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/
题目地址：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
题目描述
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
- You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
- After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
Input: [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]
题目大意
股票交易的原则是必须先买然后再卖，在买入之前必须至少休息一天。求最后能得到的最大收益。
解题方法
动态规划
感觉自己DP的能力还是太弱，越是这样越需要迎难而上。
这个题和714. Best Time to Buy and Sell Stock with Transaction Fee比较像。做题方法都是使用了两个数组：
- cash 该天结束手里没有股票的情况下，已经获得的最大收益
- hold 该天结束手里有股票的情况下，已经获得的最大收益
状态转移方程式这样的：
cash[i]代表的是手里没有股票的收益，这种可能性是今天卖了或者啥也没干。max(昨天手里有股票的收益+今天卖股票的收益，昨天手里没有股票的收益)， 即max(sell[i - 1], hold[i - 1] + prices[i])；
hold[i]代表的是手里有股票的收益，这种可能性是今天买了股票或者啥也没干，今天买股票必须昨天休息。所以为max(今天买股票是前天卖掉股票的收益-今天股票的价格，昨天手里有股票的收益）。即max(hold[i - 1], sell[i - 2] - prices[i])。
另外需要注意的是，题目说的是昨天卖了股票的话今天不能买，对于开始的第一天，不可能有卖股票的行为，所以需要做个判断。
该算法的时间复杂度是O(n)，空间复杂度是O(n)。
代码如下：
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices: return 0
sell = [0] * len(prices)
hold = [0] * len(prices)
hold[0] = -prices[0]
for i in range(1, len(prices)):
sell[i] = max(sell[i - 1], hold[i - 1] + prices[i])
hold[i] = max(hold[i - 1], (sell[i - 2] if i >= 2 else 0) - prices[i])
return sell[-1]
如果使用O(1)的空间复杂度，那么就可以写成下面这样：
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices: return 0
prev_sell = 0
curr_sell = 0
hold = -prices[0]
for i in range(1, len(prices)):
temp = curr_sell
curr_sell = max(curr_sell, hold + prices[i])
hold = max(hold, (prev_sell if i >= 2 else 0) - prices[i])
prev_sell = temp
return curr_sell
C++解法如下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
const int N = prices.size();
if (N == 0) return 0;
// cash[i] means the max profit if I dont have stock on day i
vector<int> cash(N, 0);
// stock[i] means the max profit if I have stock on day i
vector<int> stock(N, 0);
stock[0] = -prices[0];
for (int i = 1; i < N; i++) {
cash[i] = max(stock[i - 1] + prices[i], cash[i - 1]);
stock[i] = max((i >= 2 ? cash[i - 2] : 0) - prices[i], stock[i - 1]);
}
return cash[N - 1];
}
};
参考资料：
日期
2018 年 9 月 12 日 —— 做题还是要有耐心
2019 年 1 月 3 日 —— 2019年已经过去1%
最新文章
- C语言 · 高精度加法
- mac 10.11.6 自带apache配置记录
- ELK系统中kibana展示数据的时区问题
- android中versionCode&versionName
- MongoDB新增及查询数据(一)
- ERROR 2002 (HY000): Can't connect to local MySQL server through socket '/var/lib
- linux ubuntu系统下，adb不是内部命令 （如何才能让adb命令可以使用）
- centos7安装mysql
- 关于SVN版本控制器的问题与解决方法
- 细谈最近上线的Vue2.0项目（一）
- Ocelot中文文档-GraphQL
- C# deep copy List
- sprite kit -- 从入门到淡定
- Set接口HashSet实现类
- [Python] 03 - Lists, Dictionaries, Tuples, Set
- C++中虚函数的作用
- Mockplus3.5.0.1新增标注功能
- 轻量级MVVM框架 Stylet
- Codeforces731C(SummerTrainingDay06-M 并查集)
- Java Web开发中用Tomcat部署项目的三种方法