[LeetCode]买卖股票的时机系列

题目

121. 买卖股票的最佳时机
122. 买卖股票的最佳时机 II
123. 买卖股票的最佳时机 III
188. 买卖股票的最佳时机 IV
309. 最佳买卖股票时机含冷冻期
714. 买卖股票的最佳时机含手续费

解题思路

动态规划。参考
三状态 DP:dp[i][k][s],其中 s = 0, 1。表示时刻 i,最多可以进行 k 次交易的前提下,当前持有或未持有股票,所得到的最大收益。
则转移方程为:

意为保持上个状态不变或者改变(购买或出售)分别带来收益的最大值。
初始化:

1
2
3
4
5
dp[-1][k][0]=0  表示还未开始,利润为 0
dp[-1][k][1]=-inf 表示还未开始,但已经持有股票,不可能状态,赋值为 -inf

dp[i][0][0]=0 表示不允许交易,利润为 0
dp[i][0][1]=-inf 表示不允许交易,但已经持有股票,不可能状态,赋值为 -inf

注:dp 的第一维为时间步,可以直接压缩掉节省空间。

代码

Python 3.6

121. 买卖股票的最佳时机

只允许一次交易,故直接将 i 维和 k 维都去掉,变为两个常数,表示当前步 k=1 时的最大利润,而更新 dp_i_1 时需要买入时,直接从 0 去减价格,因为 k=0 时利润永远为 0

1
2
3
4
5
6
7
8
9
10
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if length < 2:
return 0
dp_i_0, dp_i_1 = 0, -prices[0]
for i in range(1, length):
dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])
dp_i_1 = max(dp_i_1, -prices[i])
return dp_i_0

122. 买卖股票的最佳时机 II

允许无限次交易,说明 kk-1 没有任何区别,故直接将这一维度删掉,更新时从自身更新。

1
2
3
4
5
6
7
8
9
10
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if length < 2:
return 0
dp_i_0 = 0
dp_i_1 = float("-inf")
for i in range(length):
dp_i_0, dp_i_1 = max(dp_i_0, dp_i_1 + prices[i]), max(dp_i_1, dp_i_0 - prices[i])
return dp_i_0

123. 买卖股票的最佳时机 III

允许最多 2 次交易,压缩 i 维后更新时与需要保证前一个状态不在使用之前被覆盖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if length < 2:
return 0
k = 2
dp = [[0] * 2 for _ in range(k + 1)]
for each_k in range(k + 1):
dp[each_k][0] = 0
dp[each_k][1] = float("-inf")
for i in range(length):
for each_k in range(k, 0, -1):
# k 从大到小更新可保证 dp 不被覆盖
dp[each_k][0] = max(dp[each_k][0], dp[each_k][1] + prices[i])
dp[each_k][1] = max(dp[each_k][1], dp[each_k - 1][0] - prices[i])
return dp[-1][0]

188. 买卖股票的最佳时机 IV

允许最多 k 次交易,若 k >= length // 2,则说明可进行无限次交易,同 122 题;否则同 123 题的 k=2 情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
length = len(prices)
if length < 2:
return 0
if k >= length // 2:
return self.max_profit_k_inf(prices)
dp = [[0] * 2 for _ in range(k + 1)]
for each_k in range(k + 1):
dp[each_k][0] = 0
dp[each_k][1] = float("-inf")
for i in range(length):
for each_k in range(k, 0, -1):
dp[each_k][0] = max(dp[each_k][0], dp[each_k][1] + prices[i])
dp[each_k][1] = max(dp[each_k][1], dp[each_k - 1][0] - prices[i])
return dp[-1][0]

def max_profit_k_inf(self, prices):
length = len(prices)
if length < 2:
return 0
dp_i_0 = 0
dp_i_1 = -prices[0]
for i in range(1, length):
dp_i_0, dp_i_1 = max(dp_i_0, dp_i_1 + prices[i]), max(dp_i_1, dp_i_0 - prices[i])
return dp_i_0

309. 最佳买卖股票时机含冷冻期

出售股票之后需要隔一天才能买,则转移方程中购买时需从上上一步来更新,多保存一个变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if length < 2:
return 0
dp_i_0 = 0
dp_i_1 = float("-inf")
dp_pre_0 = 0
for i in range(length):
tmp = dp_i_0
dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])
dp_i_1 = max(dp_i_1, dp_pre_0 - prices[i])
dp_pre_0 = tmp
return dp_i_0

714. 买卖股票的最佳时机含手续费

交易需要手续费,则在买入股票时多减去手续费即可。

1
2
3
4
5
6
7
8
9
10
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
length = len(prices)
if length < 2:
return 0
dp_i_0, dp_i_1 = 0, float("-inf")
for i in range(length):
dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])
dp_i_1 = max(dp_i_1, dp_i_0 - prices[i] - fee)
return dp_i_0

参考

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/yi-ge-tong-yong-fang-fa-tuan-mie-6-dao-gu-piao-wen/