LeetCode Best Time to Buy and Sell Stock
0121. Best Time to Buy and Sell Stock
Easy
单次交易
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
ans = 0
h = 0
for i in range(n-1, -1, -1):
if h < prices[i]:
h = prices[i]
else:
ans = max(ans, h - prices[i])
return ans
0122. Best Time to Buy and Sell Stock II
Medium
不限次数交易
def maxProfit(self, prices: List[int]) -> int:
ans = 0
for i in range(1, len(prices)):
ans += max(0, prices[i] - prices[i-1])
return ans
0123. Best Time to Buy and Sell Stock III
Hard
限制两次交易
破题
题目的复杂程度终于提升到了有点儿意思的程度，这里的关键是搞清楚“最多两次”交易的限制条件到底对我们的模型意味着什么？
可以认为，做两次交易的收益总是不差于一次交易，只要在计算模型上把一次交易视为两次交易的边缘值。
解①两遍扫描
把价格表分为两部分，左边用于第一次交易，右边用于第二次交易，这样只需要检查每个位置的两次交易之和，求一个最大值即可。可以让左边分割的串从空串开始，这样就包含了一次交易的情况。
每次分割的左边串的最大收益可以依靠前面 0121. Best Time to Buy and Sell Stock 来计算，而分割的右边串则可以预先运用同样的算法反向扫描，保存个位置的计算结果，在从左开始扫描的时候查询表即可。
def solve(prices: List[int]) -> int:
n = len(prices)
dp = [0] * (n+1)
hi = prices[-1]
for i in range(n-2, -1, -1):
if prices[i+1] > hi:
hi = prices[i+1]
if hi - prices[i] > dp[i+1]:
dp[i] = hi - prices[i]
else:
dp[i] = dp[i+1]
ans = dp[0]
lo = prices[0]
for i in range(1, n):
if prices[i-1] < lo:
lo = prices[i-1]
if prices[i] - lo + dp[i+1] > ans:
ans = prices[i] - lo + dp[i+1]
return ans
运行时间：760 ms (beats 98.06%)，内存占用：30.5 MB (beats 72.56%, ~100%)
解②规范解
在上一个解的时候，我们通过组合单次求解的方法来计算两次交易得到的最大收益，而这个单次求解的方法好像扫描一个个位置就可以进行该位置的更新，（因为当天交易收益总是零，因此是否允许当天交易都不重要），这暗示我们很可能有一个扫描每个位置就可以计算出两次交易的最大收益的模型。
这才引出对股票买卖问题的统一模型：
累积计算每次买或卖的收益，买的收益是 $-\text{price}$ ，卖的收益是买的收益加上 $\text{price}$ ，下次交易的收益基础是之前的收益。
对于两次买卖就有：
\[\begin{align} \text{buy}_1 &= \max(\text{buy}_1',\text{-price})\\ \text{sell}_1 &= \max(\text{buy}_1',\text{price})\\ \text{buy}_2 &= \max(\text{sell}_1',\text{-price})\\ \text{sell}_2 &= \max(\text{buy}_2',\text{price})\\ \end{align}\]也就是：$\text{buy}_1 \rightarrow \text{sell}_1 \rightarrow \text{buy}_2 \rightarrow \text{sell}_2$
有必要解释下，按照自然流程，两次交易至少应该是第一天 $\text{buy}_1$ ，第二天 $\text{sell}_1$ ，第三天 $\text{buy}_2$，第四天 $\text{sell}_2$，是一个 $4$ 天的窗口，但是这需要额外检查下数据长度，而把这些操作压缩到一天，并不影响结果，而且可以适应长度不足 $4$ 的情况。1
def solve(prices: List[int]) -> int:
buy1 = -prices[0]
sell1 = 0 # prices[0]+buy1
buy2 = -prices[0]
sell2 = 0 # prices[0]+buy2
for price in prices[1:]:
if buy1 < -price:
buy1 = -price
elif sell1 < buy1+price:
sell1 = buy1+price
if buy2 < sell1-price:
buy2 = sell1-price
elif sell2 < buy2+price:
sell2 = buy2+price
return sell2
运行时间：670 ms (beats 99.76%)，内存占用：30.5 MB (beats 88.72%, ~100%) 。
这个统一模型在一遍扫描就解决了问题，并且省掉了前面的 $O(n)$ 的内存占用2 。
0188. Best Time to Buy and Sell Stock IV
Hard
上面问题的一般化，不是限制两次交易，而是给定的参数 $k$ 次。
def solve(k: int, prices: List[int]) -> int:
buy = [-prices[0]] * k
sell = [0] * (k+1) # buy[i] - sell[i+1]
for price in prices:
for i in range(k):
if buy[i] < sell[i]-price:
buy[i] = sell[i]-price
elif sell[i+1] < buy[i]+price:
sell[i+1] = buy[i]+price
return sell[-1]
运行时间：59 ms (Beats 99.16%, ~100%)，内存占用：16.36MB (Beats 82.07%，~100%)。
0309. Best Time to Buy and Sell Stock with Cooldown
Medium
不限次交易，有冷冻期
破题
购买冷冻期机制的引入改变了整个的模型，使得我们不能像前面的那个无限次数交易那样简单统计所有增量，就可以得到答案。
如果遵循股票买卖整个系列的顺序来做题，题解可能格外困难，因为很容易受到前面解题思路的影响，而重构整个模型并没有那么直观，因此我认为应该把这道题标记为 Hard 难度。
因此，让我们先从最简单地、最基本地方法开始：一个基于递归，使用记忆化优化的，穷举所有可能的解决方法。
解①递归记忆化
逐个读取价格表，分两个模式：等待购入和等待卖出。下面分别用 $\text{Buy}$ 和 $\text{Sell}$ 表示这两个模式，在 $\text{Buy}$ 模式下有两种选择：在当前价格日卖出和下一天再说，同样地 $\text{Sell}$ 模式也有两种选择，以当前价格卖出和下一天再说。
from enum import Enum, auto
from functools import cache
from typing import List
class Mode(Enum):
Buy = auto(),
Sell = auto()
def solve(prices: List[int]) -> int:
n = len(prices)
@cache
def recur(mode: Mode, i: int) -> int:
if i >= n:
return 0
if mode is Mode.Buy:
cand1 = -prices[i] + recur(Mode.Sell, i+1)
cand2 = recur(Mode.Buy, i+1)
else:
cand1 = prices[i] + recur(Mode.Buy, i+2)
cand2 = recur(Mode.Sell, i+1)
return max(cand1, cand2)
return recur(Mode.Buy, 0)
运行时间：52 ms (beats 44.28%, ~100%)，内存占用：21.06 MB (beats 31.05%)。
解②迭代DP
上面的递归实现，可以帮助我们理清普通 DP 版本的实现思路。
对于交易有限次数的股票模型，可以穷举所有所有轮次买和卖的状态，但是对于不限次数的模型，则不能这样穷举，只能区分买和卖，不能辨别轮次。
尝试从正面看这个问题，分别用 buy 和 sell 两个数组代表一个前缀价格串上的最后操作是买或卖带来的最大收益。
这样，
-
买的最大收益是要比较前一天买的最大收益（意味着当前没有买卖）以及包含冷冻期在内的卖的最大收益加上当前价格；
-
卖的最大收益则是前一天卖的最大收益（意味着当前没有买卖）或者前一天买的最大收益加上当前价格（当前卖出）
def solve(prices: List[int]) -> int:
n = len(prices)
if n == 1:
return 0
prices.append(0)
buy = [0] * (n+1)
buy[0] = -prices[0]
buy[1] = max(buy[0], -prices[1])
sell = [0] * n
for i in range(n-1):
buy[i + 2] = max(buy[i+1], sell[i] - prices[i + 2])
sell[i + 1] = max(sell[i], buy[i] + prices[i + 1])
return sell[n - 1]
运行时间：36 ms (beats 98.07%, ~100%)，内存占用：16.39 MB (beats 99.34%) 。
当然，仔细观察代码，会发现 $O(n)$ 的内存占用是不必要的，实际上只需要维护三个持久变量：$\text{buy}_0$, $\text{buy}_1$ 和 $\text{sell}_0$ 。
def solve(prices: List[int]) -> int:
n = len(prices)
if n == 1:
return 0
prices.append(0)
buy0 = -prices[0]
buy1 = max(buy0, -prices[1])
sell0 = 0
for i in range(n-1):
buy2 = max(buy1, sell0 - prices[i + 2])
sell1 = max(sell0, buy0 + prices[i + 1])
sell0 = sell1
buy1, buy0 = buy2, buy1
return sell0
运行时间：45 ms (beats 79.16%, ~100%)，内存占用：16.56 MB (beats 87.33%. ~100%) 。
0714. Best Time to Buy and Sell Stock with Transaction Fee
Medium
不限次交易，有交易费
解①状态DP
直接按照前面交易冻结日的股票交易模型，易得
def solve(prices: List[int], fee: int) -> int:
n = len(prices)
buy = -prices[0]
sell = 0
for price in prices[1:]:
buy1 = max(buy, sell-price)
sell1 = max(sell, buy+price-fee)
buy = buy1
sell = sell1
return sell
运行时间：566 ms (beats 77%, ~100%)，内存占用：23.7 MB (beats 67.29%, ~100%) 。
解②贪心
但是还是有方法利用像 0122. Best Time to Buy and Sell Stock 问题那样直接地算法来解决。
只需要把交易费用加在购入价格上即可。
注意这里的 $\text{buy}$ 区别于分状态 DP 问题里面的 $\text{buy}$ ，它表示得不是购入的最大收益，而是最低价格。
def solve(prices: List[int], fee: int) -> int:
buy = prices[0]+fee
ans = 0
for price in prices[1:]:
if price + fee < buy:
buy = price + fee
elif price > buy:
ans += price-buy
buy = price
return ans
运行时间：495 ms (beats 99.5%, ~100%)，内存占用：23.7 MB (beats 67.29%, ~100%) 。
注解
