Leetcode Link: 123. 买卖股票的最佳时机 III - 力扣（LeetCode）
题目
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
解法一
从暴力递归到动态规划
暴力递归
本题属于从左到右的尝试模型，但是是比较复杂的。
如何思考子问题的分类讨论，可以先尝试画一下问题的结构树。
对于 idx 天，其树的分支情况取决于当前是否持有股票。 如果持有，则考虑今天卖还是不卖 如果没有，则考虑今天买还是不买
最后，加入部分限制条件：1) 只能买卖 2 次; 2) 卖出的时候记得加上
class Solution:
def maxProfit(self, prices: List[int]) -> int:
return self.process(prices, -1, 2, 0)
# n: 还能卖出 n 次
# cost: 买入的价格, -1 表示没买
# 在第 idx 天，选择买入还是卖出。
# 返回的是从 [idx..n] 的最大利润
def process(self, prices, cost, n, idx):
# base case, 买卖两次了或者日期结束
if n == 0:
return 0
if idx == len(prices):
return 0
if cost == -1: #### 已经买入股票的情况
p1 = self.process(prices, cost, n, idx+1) # 今天也不买
p2 = self.process(prices, prices[idx], n, idx+1) # 今天买入
else: #### 已经卖出股票的情况
p1 = self.process(prices, cost, n, idx+1) # 今天不卖
p2 = self.process(prices, -1, n-1, idx+1) + (prices[idx]-cost) # 今天卖出
return max(p1, p2)为什么
n不能表示还能买入的次数？其实是可以的，但是如果n表示买入后，是有一点逻辑问题的（买入第一次n=1,买入第二次n=0），买入后就立刻返回了。
然而，依靠上面的代码我们改 dp 有点麻烦，麻烦的点在于
- cost 多大? 定义 dp 表的大小很麻烦
- cost 还有 -1 的取值，怎么弄？要 cost 维度所有的值+1？更复杂了。或者弄两个dp表？抱歉，我暂时没相通，似乎可行，但是我想了很久了
- 为了解决 2, 添加一个新的参数
state来表示现在是否持有股票？那么这就变成了四维 dp，我都想不出来怎么更新…
由于以上问题，我们尝试改写一下代码，思考如下问题，cost 是必需的参数吗？
显然不是，对于利润，我们可以认为 cost = price[i] - price[j] (i 卖出, j 卖出)，即我们买入的当天减去花销，就能避免 cost 参数了。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
return self.process(prices, 0, 2, 0)
# n: 还能卖出 n 次
# state: 是否持有股票
# 在第 idx 天，选择买入还是卖出。
# 返回的是从 [idx..n] 的最大利润
def process(self, prices, state, n, idx):
if n == 0:
return 0
if idx == len(prices):
return 0
if state == 0: # 当前不持有股票
p1 = self.process(prices, state, n, idx+1) # 今天也不买
p2 = self.process(prices, 1, n, idx+1) - prices[idx] # 今天买入
else: #### 已经卖出股票的情况
p1 = self.process(prices, state, n, idx+1) # 今天不卖
p2 = self.process(prices, 0, n-1, idx+1) + prices[idx] # 今天卖出
return max(p1, p2)至此，后面改写 dp 就简单了。
动态规划
几个需要注意的点
- 显然，该dp是三维的dp表
- 直接看暴力递归的代码似乎有点乱，不知道谁先更新，此时手写 dp 表的依赖关系
- 显然，所有的层都依赖下一层 (i+1)，所以至此就好说了。
- 注意边界的溢出情况，以及dp表的大小定义。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# [state, n, idx]
dp=[[[0 for _ in range(len(prices)+1)] for _ in range(3)] for _ in range(2)]
for i in range(len(prices)-1, -1, -1):
for n in range(3):
dp[0][n][i] = max(dp[1][n][i+1]-prices[i], dp[0][n][i+1])
if n-1 >= 0: # 注意溢出情况
dp[1][n][i] = max(dp[0][n-1][i+1]+prices[i], dp[1][n][i+1])
else:
dp[1][n][i] = dp[1][n][i+1]
return dp[0][2][0]