题目
- 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 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 。
动态规划
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
n = len(prices)
# 初始化动态规划数组
dp = [[[0] *2 for _ in range(k+1)] for _ in range (n)]
for i in range(1,n):
for j in range(1,k+1):#k+1才取得到k值
#base case
dp[0][j][0] = 0 # 第一天不持有股票，利润为0
dp[0][j][1] = -prices[0] # 第一天持有股票，利润为-buy
#状态转移
dp[i][j][0]=max (dp[i-1][j][0],dp[i-1][j][1]+prices[i])# 不持有股票的情况，取前一天也不持有股票和前一天持有股票但今天卖出的最大利润
dp[i][j][1]=max (dp[i-1][j][1],dp[i-1][j-1][0]-prices[i])# 持有股票的情况，取前一天也持有股票和前一天不持有股票但今天买入的最大利润，交易次数k减一
return dp[n-1][k][0] # 最后一天，进行了k次交易，不持有股票的利润即为最大利润
优化
- 待更新...