代码随想录算法训练营第五十二天|188.买卖股票的最佳时机Ⅳ

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

代码随想录

. – 力扣（LeetCode）

 这道题目与之前题目不同的是：限制了k笔交易

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

确定dp数组以及下标的含义

每多交易一次就会多两个状态，上一题中可以完成2笔交易，就有1+2*2个状态，那么完成k笔交易，就有1+2*k个状态

dp数组的大小：len（prices）* （2*k+1）

使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]

j的状态表示为：

• 0 表示不操作
• 1 第一次买入
• 2 第一次卖出
• 3 第二次买入
• 4 第二次卖出
• 5 第三次买入
• 6 第三次买出

大家应该发现规律了吧 ，除了0以外，偶数就是卖出，奇数就是买入。

题目要求是至多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以了。

确定递推公式

达到dp[i][1]状态，有两个具体操作：

• 操作一：第i天买入股票了，那么dp[i][1] = dp[i – 1][0] – prices[i]
• 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i – 1][1]

选最大的，所以 dp[i][1] = max(dp[i – 1][0] – prices[i], dp[i – 1][1]);

同理dp[i][2]也有两个操作：

• 操作一：第i天卖出股票了，那么dp[i][2] = dp[i – 1][1] + prices[i]
• 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i – 1][2]

所以dp[i][2] = max(dp[i – 1][1] + prices[i], dp[i – 1][2])

同理可以类比剩下的状态，代码如下：

本题和动态规划：123.买卖股票的最佳时机III (opens new window)最大的区别就是这里要类比j为奇数是买，偶数是卖的状态。

要注意状态之间的顺序性

比如第2次持有状态，是依赖于之前天就是第二次持有，或者是当前第二次买入，那么前一天就是第一次不持有的状态；如果是第二次不持有，当天卖出的话，那么前一天就是第一次持有

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        
        dp = [[0 for _ in range(2*k + 1)] for i in range(len(prices))]
        #dp[i][0] 不操作，dp[i][1]：第一次持有 ，dp[i][2]：第一次不持有 ，dp[i][3]：第二次持有 ，dp[i][4]： 第二次不持有
        
        for j in range(0,2*k,2):
            dp[0][j+1] =  -prices[0]
        for i in range(1,len(prices)):
            for j in range(0,2*k,2):
                dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j]-prices[i]) #第j次持有
                dp[i][j+2] = max(dp[i-1][j+2],dp[i-1][j+1]+prices[i])#第j次不持有
        return dp[-1][-1] #这个结果包含了第一次买卖的最大值