1. 题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

2. 思路（动态规划）

在股票系列的第三个题中，,规定的股票交易次数为2。而这个题中是股票交易次数k为任意值。因此可以直接用上一题的代码：买卖股票的最佳时机|||
不过需要优化一下，否则会超内存。

优化

考虑一次股票买卖，第一天买入，第二天卖出，因此一次股票买卖需要两天。当给定的k大于len(prices)//2时，只要后一天的价格大于前一天的价格，就进行一次股票买卖。反正是不会超过限制的股票交易次数。当k小于len(prices)//2时，就可以利用上一题的代码，不过得需要修正一下。

2.1 python代码

class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if len(prices) == 0:
return 0
if k >= len(prices)//2:
profit = 0
for i in range(len(prices)-1):
if prices[i+1] > prices[i]:
profit += (prices[i+1]-prices[i])
return profit
else:
n = len(prices)
dp = [[[0 for i in range(2)] for i in range(k+1)] for i in range(n)]
for i in range(k+1):
# 不管k等于几，第0天不持有股票的利润为0，持有股票的利润为-prices[0]（卖股票的钱）
dp[0][i][0] = 0
dp[0][i][1] = -prices[0]
for i in range(1,n):
for j in range(1,k+1):
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])
return dp[n-1][k][0]