188. 买卖股票的最佳时机 IV（难）

• 题目
• 动态规划
• 优化

题目

• 给你一个整数数组 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次交易，不持有股票的利润即为最大利润

优化

• 待更新...