给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1:
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
思路：
1.确定状态 某一天的状态分为两种一种dp[i][0]代表该天交易后不持有股票，dp[i][1]代表该天交易后持有股票
2.状态转移方程
--第i天没有股票，其状态由第i-1天持有股票和第i-1天不持有股票
持有股票dp[i-1][1]+prices[i]-fee
不持有股票dp[i-1][0]
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]-fee)
--第i天有股票，其状态由第i-1天持有股票和第i-1天不持有股票
持有股票dp[i-1][1]
不持有股票,需要买入股票dp[i-1][0]- prices[i]
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
3.边界条件
第0天[0,-prices[0]]，第n-1天卖出股票利润最大
4.计算顺序--顺序计算
n = len(prices)
# 定义一个n行2列的数组
dp = [[0, -prices[0]]] + [[0, 0] for _ in range(n - 1)]
for i in range(1, n):
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 - 1][0] - prices[i])
return dp[n - 1][0]
买股票最佳时机
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3
1.确定状态
buy[i][j]代表第i天恰好j笔交易，手中持有股票；
sell[i][j]代表第i天恰好进行j笔交易，手中没有股票
根据是否是第i天买入的分为两种情况
--不是第i天买入的
--是第i天买入的并且恰好进行了j笔交易
2.状态转移方程
buy[i][j] = max(buy[i-1][j],sell[i-1][j]-prices[i])
sell[i][j] = max(sell[i-1][j],buy[i-1][j-1]+prices[i])
3.确定边界条件
第0天持有股票为buy[0][0]=-prices[0]
第0天不持有股票为sell[0][0] = 0
buy[0][1...k] = 非法可设置为负无穷
sell[0][1...k] = 非法可设置为负无穷
进行0笔交易时,第i天开始买股票
buy[i][0] = max(buy[i-1][0],sell[i-1][j]-prices[i])
优化n个股票最多进行n/2次交易
if not prices:
return 0
n = len(prices)
k = min(k,n//2)
# 开辟k+1 的数组
buy = [[0]*(k+1) for _ in range(n)]
sell = [[0]*(k+1) for _ in range(n)]
# 初始化
buy[0][0],0= -prices[0],sell[0][0]
for i in range(1,k+1):
buy[0][i] =sell[0][i]= float("-inf")
for i in range(1,n):
buy[i][0] = max(buy[i-1][0],sell[i-1][0]-prices[i])
for j in range(1,k+1):
buy[i][j] = max(buy[i-1][j],sell[i-1][j]-prices[i])
sell[i][j] = max(sell[i-1][j],buy[i-1][j-1]+prices[i])
return max(sell[n-1])
``
