题目
- 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 K笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
分析：
状态：天数i、允许交易的最大次数k、当前持有中状态(0/1)
选择：买入、卖出、无操作
通用模板
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
# 初始化动态规划数组
dp = [[[0] * 2 for _ in range(3)] for _ in range(n)]
#base case:
dp[0][k][0]=0 # 第一天不持有股票，利润为0
dp[0][k][1]=-prices[0] # 第一天持有股票，利润为-buy
#状态转移方程：
for i in range (1,n):
for k in range (1,K)
# 不持有股票的情况，取前一天也不持有股票和前一天持有股票但今天卖出的最大利润
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
# 持有股票的情况，取前一天也持有股票和前一天不持有股票但今天买入的最大利润，交易次数k减一
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
return dp[n-1][K][0]
- 当交易次数k为1(121题)或无穷(122题)时，k对状态转移没有影响，去掉k，从三维数组变成二维数组
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
# 初始化动态规划数组
dp=[[0] * 2 for _ in range(n)]
#base case:
dp[0][0]=0 # 第一天不持有股票，利润为0
dp[0][1]=-prices[0] # 第一天持有股票，利润为-buy
#状态转移方程：
for i in range (1,n):
# 不持有股票的情况，取前一天也不持有股票和前一天持有股票但今天卖出的最大利润
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
# 持有股票的情况，取前一天也持有股票和前一天不持有股票但今天买入的最大利润，交易次数k减一
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) #当k=1时dp[i-1][0][0]=0带入
return dp[n-1][0]
- 309题，k为无穷，含冷冻期，只需要在第i天选择买入的时候，从i-2的状态转移，而不是i-1
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
- 714题，含手续费，只需要在买入或者卖出的时候减去手续费即可
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]-fee)
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
优化
- 目前上文提到的四个题，优化思路一致：用两个变量代替二维数组（持有/不持有）
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
#base case
a=0 # 第一天不持有股票，利润为0
b=-prices[0] # 第一天持有股票，利润为-buy
#动态转移
for i in range(1,n): #前面处理了第一天的情况，直接从第二天开始，可以避免下标越界的发生
a=max(a,b+prices[i]) # 不持有股票的情况，取前一天也不持有股票和前一天持有股票但今天卖出的最大利润
b=max(b,a-prices[i]) # 持有股票的情况，取前一天也持有股票和前一天不持有股票但今天买入的最大利润
return a # 最后一天不持有股票的利润即为最大利润
详细改动请见对应文章
- 当交易次数k为2(123题)或任意给定值(188题)时
- 此时k影响状态转移，不能省去，用三维数组。k=2时较小直接把所有情况列举，k为任意值时用for循环
详情见之前文章