题目
121. 买卖股票的最佳时机
122. 买卖股票的最佳时机 II
123. 买卖股票的最佳时机 III
188. 买卖股票的最佳时机 IV
309. 最佳买卖股票时机含冷冻期
714. 买卖股票的最佳时机含手续费
解题思路
动态规划。参考
三状态 DP：dp[i][k][s]，其中 s = 0, 1。表示时刻 i，最多可以进行 k 次交易的前提下，当前持有或未持有股票，所得到的最大收益。
则转移方程为：
意为保持上个状态不变或者改变（购买或出售）分别带来收益的最大值。
初始化：1
2
3
4
5dp[-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 时利润永远为 01
2
3
4
5
6
7
8
9
10class 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
允许无限次交易，说明 k 与 k-1 没有任何区别，故直接将这一维度删掉，更新时从自身更新。1
2
3
4
5
6
7
8
9
10class 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
16class 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
26class 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
14class 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
10class 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