目录
LeetCode123. 买卖股票的最佳时机III
链接: 链接:123. 买卖股票的最佳时机 III - 力扣(LeetCode)
1. 思路
本题相对于LeetCode121和LeetCode122难了不少;关键在于至多买卖两次,这意味着可以买卖一次,可以买卖两次,也可以不买卖。
接来下我用动态规划五部曲详细分析一下:
1.1 确定dp数组以及下标的含义
一天一共就有五个状态,
- 没有操作
- 第一次买入的状态
- 第一次卖出的状态
- 第二次买入的状态
- 第二次卖出的状态
dp[i][j]中 i表示第i天,j为 [0 - 4] 五个状态,dp[i][j]表示第i天状态j所剩最大现金;
1.2 确定递推公式
需要注意:dp[i][1],表示的是第i天,买入股票的状态,并不是说一定要第i天买入股票,这是很多同学容易陷入的误区;
达到dp[i][1]状态,有两个具体操作:
- 操作一:第i天买入股票了,那么dp[i][1] = dp[i-1][0] - prices[i]
- 操作二:第i天没有操作,而是沿用前一天买入的状态,即:dp[i][1] = dp[i - 1][1]
那么dp[i][1]究竟选 dp[i-1][0] - prices[i],还是dp[i - 1][1]呢?
一定是选最大的,所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
同理dp[i][2]也有两个操作:
- 操作一:第i天卖出股票了,那么dp[i][2] = dp[i - 1][1] + prices[i]
- 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:dp[i][2] = dp[i - 1][2]
所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
同理可推出剩下状态部分:
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
1.3 dp数组初始化
dp[0][0]
第0天没有操作,这个最容易想到,就是0,即:dp[0][0] = 0;
dp[0][1]
第0天做第一次买入的操作,dp[0][1] = -prices[0];
dp[0][2]
第0天做第一次卖出的操作,这个初始值应该是多少呢?首先卖出的操作一定是收获利润,整个股票买卖最差情况也就是没有盈利即全程无操作现金为0,从递推公式中可以看出每次是取最大值,那么既然是收获利润如果比0还小了就没有必要收获这个利润了,所以dp[0][2] = 0;(这个解释我不是很懂)我认为可以理解成第0天买入了再卖出,价格是一样的,所以为0;
dp[0][3]
第0天第二次买入操作,初始值应该是多少呢?应该不少同学疑惑,第一次还没买入呢,怎么初始化第二次买入呢?
第二次买入依赖于第一次卖出的状态,其实相当于第0天第一次买入了,第一次卖出了,然后在买入一次(第二次买入),那么现在手头上没有现金,只要买入,现金就做相应的减少。所以第二次买入操作,初始化为:dp[0][3] = -prices[0];
dp[0][4]
可以理解为第0天完成了第一次买入,卖出,又第二次买入,卖出,总体来说利润为0;同理第二次卖出初始化dp[0][4] = 0;
1.4 确定遍历顺序
从递归公式其实已经可以看出,一定是从前向后遍历,因为dp[i],依靠dp[i - 1]的数值;
1.5 举例推导dp数组
以输入[1,2,3,4,5]为例
大家可以看到红色框为最后两次卖出的状态。
现在最大的时候一定是卖出的状态,而两次卖出的状态现金最大一定是最后一次卖出。所以最终最大利润是dp[4][4];
因为是最大的利润,不会小于第一次卖出的利润,因为大不了就day5的时候,再在同一天买进卖出,j=2的利润就等于j=4的利润率了,所以可以直接取最右下角的数即可;
2. 代码实现
# 动态规划
# time:O(N);space:O(N)
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
# dp的定义
# j 为五种状态
# 0: 无操作
# 1: 1st 买入
# 2: 1st 卖出
# 3: 2nd 买入
# 4: 2nd 卖出
# dp[i][j] 第i天,在j状态的最大金钱余额
length = len(prices)
dp = [[0]*5 for _ in range(length)]
# 初始化
dp[0][0] = 0
dp[0][1] = -prices[0]
dp[0][2] = 0
dp[0][3] = -prices[0]
dp[0][4] = 0
# 遍历
for i in range(1,length):
# 递推公式
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])
dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i])
dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i])
dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i])
return dp[length-1][4]
3. 复杂度分析
时间复杂度:O(N)
N为prices数组的长度;需要从头到尾遍历prices数组一遍;
空间复杂度:O(N)
dp数组的大小为N*5,整体来说还是O(N)的复杂度;
4. 思考与收获
(二刷再考虑看不看)还有一种优化空间的写法
class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) == 0: return 0 dp = [0] * 5 dp[1] = -prices[0] dp[3] = -prices[0] for i in range(1, len(prices)): dp[1] = max(dp[1], dp[0] - prices[i]) dp[2] = max(dp[2], dp[1] + prices[i]) dp[3] = max(dp[3], dp[2] - prices[i]) dp[4] = max(dp[4], dp[3] + prices[i]) return dp[4]
- 时间复杂度:O(n)
- 空间复杂度:O(1)
大家会发现dp[2]利用的是当天的dp[1]。 但结果也是对的;我来简单解释一下:dp[1] = max(dp[1], dp[0] - prices[i]); 如果dp[1]取dp[1],即保持买入股票的状态,那么 dp[2] = max(dp[2], dp[1] + prices[i]);中dp[1] + prices[i] 就是今天卖出。
如果dp[1]取dp[0] - prices[i],今天买入股票,那么dp[2] = max(dp[2], dp[1] + prices[i]);中的dp[1] + prices[i]相当于是尽在再卖出股票,一买一卖收益为0,对所得现金没有影响。相当于今天买入股票又卖出股票,等于没有操作,保持昨天卖出股票的状态了。这种写法看上去简单,其实思路很绕,不建议大家这么写,这么思考,很容易把自己绕进去!对于本题,把版本一的写法研究明白,足以!
Reference:代码随想录 (programmercarl.com)
本题学习时间:60分钟。
LeetCode188. 买卖股票的最佳时机IV
链接:188. 买卖股票的最佳时机 IV - 力扣(LeetCode)
1. 思路
本题可以说是LeetCode123.买卖股票的最佳时机III的进阶版,这里要求至多有K次交易;动态规划五部曲分析如下:
1.1 确定dp数组以及下标的含义
在LeetCode123.买卖股票的最佳时机III中,定义了一个二维的dp数组,题其实依然可以用一个二维dp数组;使用二维数组 dp[i][j] :第i天的状态为j,所剩下的最大现金是dp[i][j];
j的状态表示为:
- 0 表示不操作
- 1 第一次买入
- 2 第一次卖出
- 3 第二次买入
- 4 第二次卖出
- .....
大家应该发现规律了吧 ,除了0以外,偶数就是卖出,奇数就是买入。
题目要求是至多有K笔交易,那么j的范围就定义为 2 * k + 1 就可以了。
1.2 确定递推公式
还要强调一下:dp[i][1],表示的是第i天,买入股票的状态,并不是说一定要第i天买入股票,这是很多同学容易陷入的误区;
达到dp[i][1]状态,有两个具体操作:
- 操作一:第i天买入股票了,那么dp[i][1] = dp[i - 1][0] - prices[i]
- 操作二:第i天没有操作,而是沿用前一天买入的状态,即:dp[i][1] = dp[i - 1][1]
选最大的,所以 dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
同理dp[i][2]也有两个操作:
- 操作一:第i天卖出股票了,那么dp[i][2] = dp[i - 1][1] + prices[i]
- 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:dp[i][2] = dp[i - 1][2]
所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
同理可以类比剩下的状态,代码如下:
for j in range(0, 2*k-1, 2):
dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] - prices[i])
dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i])
本题和动态规划:123.买卖股票的最佳时机III (opens new window)最大的区别就是这里要类比j为奇数是买,偶数是卖的状态;
1.3 dp数组初始化
第0天没有操作,这个最容易想到,就是0,即:dp[0][0] = 0;
第0天做第一次买入的操作,dp[0][1] = -prices[0];
第0天做第一次卖出的操作,这个初始值应该是多少呢?
首先卖出的操作一定是收获利润,整个股票买卖最差情况也就是没有盈利即全程无操作现金为0,
从递推公式中可以看出每次是取最大值,那么既然是收获利润如果比0还小了就没有必要收获这个利润了。
所以dp[0][2] = 0;
第0天第二次买入操作,初始值应该是多少呢?
不用管第几次,现在手头上没有现金,只要买入,现金就做相应的减少。
第二次买入操作,初始化为:dp[0][3] = -prices[0];
所以同理可以推出dp[0][j]当j为奇数的时候都初始化为 -prices[0]
代码如下:
for j in range(1, 2*k, 2):
dp[0][j] = -prices[0]
在初始化的地方同样要类比j为偶数是卖、奇数是买的状态;
1.4 确定遍历顺序
从递归公式其实已经可以看出,一定是从前向后遍历,因为dp[i],依靠dp[i - 1]的数值;
1.5 举例推导dp数组
以输入[1,2,3,4,5],k=2为例;
最后一次卖出,一定是利润最大的,dp[prices.size() - 1][2 * k]即红色部分就是最后求解。
2. 代码实现
# 动态规划
# time:O(N*K);space:O(N*K)
class Solution(object):
def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
# 排除base case
if len(prices) == 0: return 0
length = len(prices)
# 初始化,有length行,2K+1列
dp = [[0]*(2*k+1) for _ in range(length)]
# j 为奇数的地方,代表买入,全部初始化为-prices[0]
for j in range(2*k):
if j%2: dp[0][j] = -prices[0]
# 从i=1,第一天开始遍历
for i in range(1,length):
# j 需要遍历2K个状态
for j in range(1,2*k+1):
# 如果j为奇数,代表是买入日
if j%2:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]-prices[i])
# 如果j为偶数,代表是卖出日
if j%2 == 0:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+prices[i])
return dp[length-1][2*k]
3. 复杂度分析
时间复杂度:O(N*K)
其中N为prices数组的长度,K为题目中给的最多买卖K次;for loop中需要循环N *(2K)次;
空间复杂度:O(N*K)
其中N为prices数组的长度,K为题目中给的最多买卖K次;dp数组的大小为N*(2K+1)
4. 思考与收获
有的解法是定义一个三维数组dp[i][j][k],第i天,第j次买卖,k表示买还是卖的状态,从定义上来讲是比较直观;但感觉三维数组操作起来有些麻烦,这里直接用二维数组来模拟三维数组的情况,代码看起来也清爽一些;
(二刷再考虑看不看)类似LeetCode123 ,还有一种状态压缩的写法如下:
class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: if len(prices) == 0: return 0 dp = [0] * (2*k + 1) for i in range(1,2*k,2): dp[i] = -prices[0] for i in range(1,len(prices)): for j in range(1,2*k + 1): if j % 2: dp[j] = max(dp[j],dp[j-1]-prices[i]) else: dp[j] = max(dp[j],dp[j-1]+prices[i]) return dp[2*k]
Reference:代码随想录 (programmercarl.com)
本题学习时间:80分钟。
本篇学习时间约2小时,总结字数5000+;又学习了动态规划中股票问题的两个题目,难度比之前的股票问题大了不少,IV是III的进阶版,推广到最多买卖K次了。(求推荐!)