[TOC]
不限交易次数
eg. Leetcode122
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
Solution:
1）先画状态机：
2）给出两个状态的转移方程： $$ dfs(i,0) = max(dfs(i-1,0),dfs(i-1,1)+prices[i])\
dfs(i,1) = max(dfs(i-1,1),dfs(i-1,0)-prices[i]) $$
3）递归边界 \(dfs(-1,0) = 0 \ \ \ \ \ // 第0天开始时候如果未持有股票，则利润为0 \\ dfs(-1,1) = -10**9-7 \ \ \ \ \ //第0天开始不可以持有股票\)
4）递归入口 \(max(dfs(n-1,0),dfs(n-1,1))=dfs(n-1,0)\)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
@lru_cache(maxsize=None)
def dfs(i:int,s:bool)->int:
if i<0:
return -inf if s else 0
if s:
return max(dfs(i-1,True),dfs(i-1,False)-prices[i])
return max(dfs(i-1,False),dfs(i-1,True)+prices[i])
return dfs(n-1,0)
5）翻译成递推 \(f[0][0] = 0, f[0][1] = -inf \\ f[i+1][0] = max(f[i][0],f[i][1]+prices[i])\\ f[i+1][1] = max(f[i][1],f[i][0]-prices[i])\\ return \ \ f[n][0]\) 6）空间优化-迭代
\[dp0 = 0, dp1 = -inf \\ new\_dp0 = max(dp0,dp1+prices[i])\\ dp1 = max(dp1,dp0-prices[i])\\ dp0 = new\_dp0\\ return \ \ dp0\]需要考虑到dp0还需要被用于更新dp1，不要将其覆盖掉
7）终极空间优化-覆盖
\[dp0 = 0, dp1 = -inf \\ dp0 = max(dp0,dp1+prices[i])\\ dp1 = max(dp1,dp0-prices[i])\\ return \ \ dp0\]一般来讲，可以找到一个更新顺序，是得覆盖合理
比如这里dp0被更新之后，被用于dp1更新也是合理的，无非当天买入当天卖出
8）奇怪的优化-python
\[dp0 = 0, dp1 = -inf \\ dp0,dp1 = max(dp0,dp1+prices[i]),max(dp1,dp0-prices[i])\\ return \ \ dp0\]其实可以直接使用python的多元素赋值，直接解决问题
eg. Leetcode309
给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
Solution:
1）状态机
三个状态：买入dp0，未买入dp1，冷冻dp2 \(dp0,dp1,dp2 = -inf,0,-inf\\ dp0,dp1,dp2 = max(dp0,dp1-price),max(dp1,dp2),dp0+price\\ return\ \ max(dp1,dp2)\)
3）优化
其实可以直接两个状态转移, 买入股票的状态之内从两天前的未持有状态转移而来
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
@lru_cache(maxsize=None)
def dfs(i:int,s:bool)->int:
if i<0:
return -inf if s else 0
if s:
return max(dfs(i-1,True),dfs(i-2,False)-prices[i])
return max(dfs(i-1,False),dfs(i-1,True)+prices[i])
return dfs(n-1,0)
至多/至少/恰好交易k次
eg. Leetcode188
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
Solution：
1）状态机
2）转移方程 \(dfs(i,j,0) = max(dfs(i-1,j,0),dfs(i-1,j,1)+price[i]) \\ dfs(i,j,1) = max(dfs(i-1,j,1),dfs(i-1,j-1,0)-price[i])\)
3）递归边界 \(dfs(\cdot,-1,\cdot) = -inf \ \ \ \ \ // 任何情况下，交易次数不可能为负 \\ dfs(-1,j,0) = 0 \ \ \ \ \ // 第0天开始时候如果未持有股票，则利润为0 \\ dfs(-1,j,1) = -inf \ \ \ \ \ //第0天开始不可以持有股票\)
4）递归入口 \(max(dfs(n-1,k,0),dfs(n-1,k,1)) = dfs(n-1,k,0)\)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
@lru_cache(maxsize=None)
def dfs(i:int,j:int,s:bool)->int:
if j<0:
return -inf
if i<0:
return -inf if s else 0
if s:
return max(dfs(i-1,j,True),dfs(i-2,j-1,False)-prices[i])
return max(dfs(i-1,j,False),dfs(i-1,j,True)+prices[i])
return dfs(n-1,k,0)
5）翻译为递推 \(f[\cdot][0][\cdot] = -inf, \ \ f[0][j][0] = 0,\ \ f[0][j][1] = -inf \\ f[i+1][j+1][0] = max(f[i][j+1][0],f[i][j+1][1]+prices[i])\\ f[i+1][j+1][1] = max(f[i][j+1][1],f[i][j][0]-prices[i])\\ return \ \ f[n][k+1][0]\)
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
n = len(prices)
f = [[-inf]*2 for _ in range(k+2)]
for i in range(1,k+2):
f[i][0] = 0
for i,p in enumerate(prices):
for j in range(k,-1,-1):
f[j+1][0] = max(f[j+1][0],f[j+1][1]+p)
f[j+1][1] = max(f[j+1][1],f[j][0]-p)
return f[k+1][0]
Follow up: 恰好k次
初始化改为： \(f[0][1][0] = 0\\ others = -inf\) 因为递归到 $i<0$ 时，只有 $j=0$ 才是合法的，$j>0$ 是不合法的。
Follow up: 至少k次
初始化改成： \(f[0][0][0] = 0,\ \ others = -inf \\ f[i+1][0][0] = max(f[i][0][0],f[i][0][1]+prices[i])\\ f[i+1][0][1] = max(f[i][0][1],f[i][0][0]-prices[i])\\ return \ \ f[n][k+1][0]\) 递归到「至少 0 次」时，它等价于「交易次数没有限制」
