LeetCode0188.买卖股票的最佳时机IV【困难】【Python】【动态编程】问题LeetCode假设你有一个数组，其中第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.题目给定一个数组，它的第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），本次交易可获利profit=3-0=3.思路动态规划求状态方程dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])解释：昨天没有股票，但是昨天有股票卖出dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])解释：昨天有库存，昨天没有库存。今天购买的基本情况：dp[-1][k][0]=dp[i][k][0]=0dp[-1][k][1]=dp[i][k][1]=-infk如果超过n/2，则视为inf。如果k不超过n/2，枚举k的值。空间复杂度：O(1)Python3代码类解决方案：defmaxProfit(self,k:int,prices:List[int])->int:n=len(prices)ifk>n/2:#k=infdp_i_0=0dp_i_1=float('-inf')#negativeinfinityforiinrange(n):temp=dp_i_0#昨天没有库存，但昨天有库存，今天卖出dp_i_0=max(dp_i_0,dp_i_1+prices[i])#dp_i_0和dp_i_1可以看做是变量，存放的是上次的值，也就是昨天的值#昨天有股票，昨天没有股票。今天买dp_i_1=max(dp_i_1,temp-prices[i])returndp_i_0#k<=len(prices)/2#dp=[[[0]*2]*(k+1)]*n#创建一个三维数组，这是有问题的dp=[[[0]*2for_inrange(k+1)]for_inrange(n)]foriinrange(n):forjinrange(k,0,-1):#reverseorderifi==0:dp[0][j][0]=0dp[0][j][1]=-prices[0]continue#昨天没有库存，但是昨天有库存，今天卖出了dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+prices[i])#昨天有库存，昨天没有库存。今天买。buying在这里被当做交易，所以是j-1#如果上一行代码中写了j-1，那么sale就被当做交易，运行结果不是正确答案。我不知道为什么dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i])returndp[n-1][k][0]代码地址GitHub链接参考一个方法dowstock问题
