目录
股票买卖问题
简介
在力扣上，股票买卖问题都可以通过动态规划求解，具体的题目如下：
| 序号 | 题目 | 区别 |
|---|---|---|
| 1 | 121. 买卖股票的最佳时机 | 只能交易一次 |
| 2 | 122. 买卖股票的最佳时机 II | 交易次数不受限制 |
| 3 | 123. 买卖股票的最佳时机 III | 交易次数受限制 |
| 4 | 188. 买卖股票的最佳时机 IV | 交易次数为K（可能受限，也可能无限制） |
| 5 | 309. 最佳买卖股票时机含冷冻期 | 交易次数不受限制，但包含冷冻期 |
| 6 | 714. 买卖股票的最佳时机含手续费 | 交易次数不受限制，但包含手续费 |
一种常用的方法是将「买入」和「卖出」分开进行考虑：「买入」为负收益，而「卖出」为正收益。在初入股市时，你只有「买入」的权利，只能获得负收益。而当你「买入」之后，你就有了「卖出」的权利，可以获得正收益。
显然，我们需要尽可能地降低负收益而提高正收益，因此我们的目标总是将收益值最大化。因此，我们可以使用动态规划的方法，维护在股市中每一天结束后可以获得的「累计最大收益」，并以此进行状态转移，得到最终的答案。
应用
应用1：Leetcode.121
题目
分析
设 \(dp[i]\) 表示第 \(i\) 天能获取的最大利润。
边界条件
未开始交易的时候，收益为零，即
\[dp[0] = 0 \]状态转移
显然，要获取最大的收益，我们首先想到的是在最低点买入，然后在最高点卖出，这样，我们就可以获取最大收益。
我们假设前 \(i-1\) 天的股票的最低价格是 \(price_{min}\)，由于，肯定要买入股票才会有收益，所以，对于第 \(i\) 天当前已经买入的股票，我们有两种选择：
- 保留股票，收益与前一天的收益相同，即 \(dp[i - 1]\)；
- 卖出股票，收益就是当天的价格与历史最低价格之差，即 $price[i] - price_{min} $；
所以，在第 \(i\) 天的收益，就是上述两种选择的最大值，那么状态转移方程就是：
\[dp[i] = \max(dp[i-1], prices[i] - price_{min}) \]代码实现
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [0] * n
dp[0] = 0
min_price = prices[0]
max_profit = dp[0]
for i in range(1, n):
min_price = min(min_price, prices[i])
dp[i] = max(dp[i - 1], prices[i] - min_price)
max_profit = max(max_profit, dp[i])
return max_profit
应用2：Leetcode.122
题目
分析
设 \(dp[i][0]\) 表示第 \(i\) 天不持有股票的最大利润，\(dp[i][1]\) 表示第 \(i\) 天持有股票的最大利润，设数组 \(prices\) 的长度为 \(n\) ，那么，在最后一天结束，手上不持有股票，就是最大收益，即 \(dp[n][0]\) 。
边界条件
显然，第零天不持有股票，最大收益为零，第零天持有股票，但是由于没有卖出，所以，最大收益为负无穷，即：
\[\begin{aligned} & dp[0][0] = 0 \\ & dp[0][1] = -\infty \end{aligned} \]状态转移
那么，在第 \(i\) 天结束，存在两种情况：
-
手上持有股票
- 在第 \(i-1\) 天，就已经持有有股票，第 \(i\) 天没有买入，收益与前一天的收益相同，即 \(dp[i-1][1]\)；
- 在第 \(i-1\) 天，未持有股票，在第 \(i\) 天买入股票，收益为第 \(i-1\) 天的收益与第 \(i\) 天买入的成本之差，即 \(dp[i-1][0] - prices[i-1]\) 。
综上，在第 \(i\) 天结束后，若手上持有股票，那么最大收益，就是上述两种情况的最大值，所以，状态转移方程为：
\[dp[i][1] = \max(dp[i-1][1], dp[i-1][0] - prices[i-1]) \] -
手上不持有股票
- 在第 \(i - 1\) 天手上就已经持有股票，在第 \(i\) 天结束卖出，那么收益为前一天的收益与当天卖出的股票价格之和，即 \(dp[i - 1][1] + prices[i - 1]\)；
- 在第 \(i - 1\) 天结束就已经卖出，第 \(i\) 没有进行交易，那么收益，与前一天的收益相同，即 \(dp[i - 1][0]\) 。
综上，在第 \(i\) 天结束后，若手上不持有股票，那么最大收益，就是上述两种情况的最大值，所以，状态转移方程为：
\[dp[i][0] = \max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]) \]
所以，综上，状态转移方程为：
\[\begin{aligned} dp[i][1] = \max(dp[i-1][1], dp[i-1][0] - prices[i-1])\\ dp[i][0] = \max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]) \end{aligned} \]注意，第 \(i\) 天的股票价格是 \(prices[i - 1]\) 。
代码实现
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0 for _ in range(2)] for _ in range(n + 1)]
dp[0][0] = 0
dp[0][1] = -float("inf")
for i in range(1, n + 1):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1])
return dp[n][0]
应用3：Leetcode.123
题目
分析
设 \(dp[i][k][0]\) 表示最大交易次数为 \(k\) ，第 \(i\) 天结束了，手上持不有股票的最大收益；\(dp[i][k][1]\) 表示最大交易次数为 \(k\) ，第 \(i\) 天结束了，手上持有股票的最大收益。
边界条件
显然，不管最大交易次数为多少次，第零天不持有股票，最大收益为零，第零天持有股票，但是由于没有卖出，所以，最大收益为负无穷，即：
\[\begin{aligned} & dp[0][k][0] = 0 \\ & dp[0][k][1] = -\infty \end{aligned} \]状态转移
那么，假设最大交易次数限制为 \(k\) ，在第 \(i\) 天结束，存在两种情况：
-
手上持有股票
- 在第 \(i-1\) 天，就已经持有有股票，第 \(i\) 天没有买入，收益与前一天的收益相同，即 \(dp[i - 1][k][1]\)；
- 在第 \(i-1\) 天，未持有股票，在第 \(i\) 天买入股票，收益为第 \(i-1\) 天的收益与第 \(i\) 天买入的成本之差，即 \(dp[i-1][k - 1][0] - prices[i - 1]\) 。
综上，在第 \(i\) 天结束后，若手上持有股票，那么最大收益，就是上述两种情况的最大值，所以，状态转移方程为：
\[dp[i][1] = \max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i-1]) \] -
手上不持有股票
- 在第 \(i - 1\) 天手上就已经持有股票，在第 \(i\) 天结束卖出，那么收益为前一天的收益与当天卖出的股票价格之和，也就是说，前一天已经完成了 \(k-1\) 次交易，最后一天完成 \(1\) 次交易，即 \(dp[i - 1][k - 1][1] + prices[i - 1]\)；
- 在第 \(i - 1\) 天结束就已经卖出，第 \(i\) 没有进行交易，那么收益，与前一天的收益相同，也就是说，前一天就已经完成了 \(k\) 次交易，即 \(dp[i - 1][k][0]\) 。
综上，在第 \(i\) 天结束后，若手上不持有股票，那么最大收益，就是上述两种情况的最大值，所以，状态转移方程为：
\[dp[i][0] = \max(dp[i - 1][k][0], dp[i - 1][k - 1][1] + prices[i - 1]) \]
所以，综上，状态转移方程为：
\[\begin{aligned} &dp[i][k][0] = max(dp[i - 1][k][0], \ dp[i - 1][k][1] + prices[i - 1]) \\ &dp[i][k][1] = max(dp[i - 1][k][1], \ dp[i - 1][k - 1][0] - prices[i - 1]) \end{aligned} \]对于本题，我们令 \(k = 2\) 即可，并依次枚举 \(k = 1, 2\) 的场景即可。
代码实现
class Solution:
def maxProfit(self, prices: List[int]) -> int:
K = 2
n = len(prices)
dp = [[[0 for _ in range(2)] for _ in range(K + 1)] for _ in range(n + 1)]
for k in range(1, K + 1):
dp[0][k][0] = 0
dp[0][k][1] = -float("inf")
for i in range(1, len(n + 1):
for k in range(1, K + 1):
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i - 1])
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i - 1])
return dp[n][K][0]
应用4：Leetcode.188
题目
分析
假设数组 \(prices\) 的长度为 \(n\) ，即天数为 \(n\) ，容易看出，一次交易包含买入和卖出，至少需要两天，也就是说，有效的限制 \(k\) 需要满足 \(k \le \frac{n}{2}\)。否则，就没有约束作用了，相当于没有限制了。
所以，按照 \(K\) 是否有效两种情况，这里直接套用前面的模板即可。
代码实现
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if k == 0:
return 0
if k > len(prices) // 2:
return self.maxProfit1(prices)
else:
return self.maxProfit2(k, prices)
def maxProfit1(self, prices: List[int]) -> int:
""" 没有交易次数限制的最大收益
"""
n = len(prices)
dp = [[0 for _ in range(2)] for _ in range(n + 1)]
dp[0][0] = 0
dp[0][1] = -float("inf")
for i in range(1, n + 1):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1])
return dp[-1][0]
def maxProfit2(self, K: int, prices: List[int]) -> int:
""" 最多交易K次的最大收益
"""
n = len(prices)
dp = [[[0 for _ in range(2)] for _ in range(K + 1)] for _ in range(n + 1)]
for k in range(1, K + 1):
dp[0][k][0] = 0
dp[0][k][1] = -float("inf")
for i in range(1, n + 1):
for k in range(1, K + 1):
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i - 1])
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i - 1])
return dp[-1][k][0]
应用5：Leetcode.309
题目
分析
设 \(dp[i][0]\) 表示第 \(i\) 天不持有股票的最大利润，\(dp[i][1]\) 表示第 \(i\) 天持有股票的最大利润，设数组 \(prices\) 的长度为 \(n\) ，那么，在最后一天结束，手上不持有股票，就是最大收益，即 \(dp[n][0]\) 。
注意，这里的「处于冷冻期」指的是在第 \(i\) 天结束之后的状态。也就是说：如果第 \(i\) 天结束之后处于冷冻期，那么第 \(i + 1\) 天无法买入股票。
边界条件
显然，第零天不持有股票，最大收益为零，第零天持有股票，但是由于没有卖出，所以，最大收益为负无穷，即：
\[\begin{aligned} & dp[0][0] = 0 \\ & dp[0][1] = -\infty \end{aligned} \]状态转移
由于股票买卖需要间隔一天作为冷冻期，所以从卖出的状态转移时，中间要间隔一天。
那么，在第 \(i\) 天结束，存在两种情况：
-
手上持有股票
- 在第 \(i-1\) 天，就已经持有有股票，第 \(i\) 天没有买入，收益与前一天的收益相同，即 \(dp[i-1][1]\)；
- 在第 \(i-2\) 天，不持有股票，在第 \(i\) 天买入股票，收益为第 \(i-2\) 天的收益与第 \(i\) 天买入的成本之差，即 \(dp[i-2][0] - prices[i-1]\) 。
因为，如果要第 \(i\) 天买入股票，那么，我们就要保证第 \(i - 1\) 天手上不持有股票，且不处于冷冻期，因此，必须要保证第 \(i-2\) 天，就不持有股票。
综上，在第 \(i\) 天结束后，若手上持有股票，那么最大收益，就是上述两种情况的最大值，所以，状态转移方程为：
\[dp[i][1] = \max(dp[i - 1][1], dp[i - 2][0] - prices[i - 1]) \] -
手上不持有股票
- 在第 \(i - 1\) 天手上就已经持有股票，在第 \(i\) 天结束卖出，那么收益为第 \(i - 1\) 天的收益与当天卖出的股票价格之和，即 \(dp[i - 1][1] + prices[i - 1]\)；
- 在第 \(i - 1\) 天结束就已经卖出，第 \(i\) 没有进行交易，那么收益，与第 \(i - 1\) 天的收益相同，即 \(dp[i - 1][0]\) 。
综上，在第 \(i\) 天结束后，若手上不持有股票，那么最大收益，就是上述两种情况的最大值，所以，状态转移方程为：
\[dp[i][0] = \max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]) \]
所以，综上，状态转移方程为：
\[\begin{aligned} dp[i][1] = \max(dp[i - 1][1], dp[i - 2][0] - prices[i - 1])\\ dp[i][0] = \max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]) \end{aligned} \]代码实现
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0 for _ in range(2)] for i in range(n + 1)]
dp[0][0] = 0
dp[0][1] = -float("inf")
for i in range(1, n + 1):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1])
dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i - 1])
return dp[n][0]
应用6：Leetcode.714
题目
分析
设 \(dp[i][0]\) 表示第 \(i\) 天不持有股票的最大利润，\(dp[i][1]\) 表示第 \(i\) 天持有股票的最大利润，设数组 \(prices\) 的长度为 \(n\) ，那么，在最后一天结束，手上不持有股票，就是最大收益，即 \(dp[n][0]\) 。
边界条件
显然，第零天不持有股票，最大收益为零，第零天持有股票，但是由于没有卖出，所以，最大收益为负无穷，即：
\[\begin{aligned} & dp[0][0] = 0 \\ & dp[0][1] = -\infty \end{aligned} \]状态转移
那么，在第 \(i\) 天结束，存在两种情况：
-
手上持有股票
- 在第 \(i-1\) 天，就已经持有有股票，第 \(i\) 天没有买入，收益与前一天的收益相同，即 \(dp[i-1][1]\)；
- 在第 \(i-1\) 天，不持有股票，在第 \(i\) 天买入股票，收益为第 \(i-1\) 天的收益与第 \(i\) 天买入的成本之差，即 \(dp[i-1][0] - prices[i-1]\) 。
综上，在第 \(i\) 天结束后，若手上持有股票，那么最大收益，就是上述两种情况的最大值，所以，状态转移方程为：
\[dp[i][1] = \max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]) \] -
手上不持有股票
- 在第 \(i - 1\) 天，就已经持有股票，第 \(i\) 天结束卖出，那么收益为第 \(i - 1\) 天的收益与当天卖出的股票收益之和，即 \(dp[i - 1][1] + prices[i - 1] - fee\)；
注意，卖出股票的收益等于卖出时股票的价格减去手续费。 - 在第 \(i - 1\) 天，不持有股票，第 \(i\) 没有进行交易，那么收益，与第 \(i - 1\) 天的收益相同，即 \(dp[i - 1][0]\) 。
综上，在第 \(i\) 天结束后，若手上不持有股票，那么最大收益，就是上述两种情况的最大值，所以，状态转移方程为：
\[dp[i][0] = \max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1] - fee) \] - 在第 \(i - 1\) 天，就已经持有股票，第 \(i\) 天结束卖出，那么收益为第 \(i - 1\) 天的收益与当天卖出的股票收益之和，即 \(dp[i - 1][1] + prices[i - 1] - fee\)；
所以，综上，状态转移方程为：
\[\begin{aligned} & dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]) \\ & dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1] - fee) \end{aligned} \]代码实现
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0 for _ in range(2)] for i in range(n + 1)]
dp[0][0] = 0
dp[0][1] = -float("inf")
for i in range(1, n + 1):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]- fee)
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1])
return dp[-1][0]
参考：
- https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/zui-jia-mai-mai-gu-piao-shi-ji-han-leng-dong-qi-4/
- https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247494095&idx=4&sn=7aed55b22e93c0e43b83172923b51acc&scene=21#wechat_redirect