【数据结构与算法】【LeetCode】【动态规划】309.最佳买卖股票时机含冷冻期

dp组

题目

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

题解

这是一道典型的 DP 问题， DP 问题的核心是找到状态和状态转移方程。

这道题目的状态似乎比我们常见的那种 DP 问题要多，这里的状态有 buy sell cooldown 三种， 我们可以用三个数组来表示这这三个状态，buy,sell, cooldown

• buy[i]表示第 i 天，且以 buy 结尾的最大利润
• sell[i]表示第 i 天，且以 sell 结尾的最大利润
• cooldown[i]表示第 i 天，且以 sell 结尾的最大利润

我们思考一下，其实 cooldown 这个状态数组似乎没有什么用，因此 cooldown 不会对profit产生 任何影响。 我们可以进一步缩小为两种状态。

• buy[i] 表示第 i 天，且以 buy 或者 coolwown 结尾的最大利润
• sell[i] 表示第 i 天，且以 sell 或者 cooldown 结尾的最大利润

对应的状态转移方程如下：

buy[i] = max(buy[i - 1], sell[i - 2] - prices[i])
sell[i] =max(sell[i - 1], buy[i - 1] + prices[i])

分析：buy[i]对应第 i 的 action 只能是 buy 或者 cooldown。

• 如果是 cooldown，那么 profit 就是 buy[i - 1]
• 如果是 buy，那么就是前一个卖的profit减去今天买股票花的钱，即 sell[i -2] - prices[i]

  注意这里是 i - 2，不是 i-1 ，因为有 cooldown 的限制

sell[i]对应第 i 的 action 只能是 sell 或者 cooldown

• 如果是 cooldown，那么 profit 就是 sell[i - 1]
• 如果是 sell，那么就是前一次买的时候获取的利润加上这次卖的钱，即 buy[i - 1] + prices[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def maxProfit(self, prices) -> int:
        if prices==None or len(prices)<=1:
            return 0
        n=len(prices)
        # 定义状态变量
        buy=[0]*n
        sell=[0]*n
        # 
        buy[0]=-prices[0]
        buy[1]=max(-prices[0],-prices[1])
        sell[0]=0
        sell[1]=max(0,prices[1]-prices[0])
        
        for i in range(2,n):
            #状态转移方程
            # 第i天只能是买或者cooldown
            buy[i]=max(buy[i-1],sell[i-2]-prices[i])
            
            sell[i]=max(sell[i-1],buy[i-1]+prices[i])
        return max(buy[-1],sell[-1])

1
2
3

a= Solution()
prices=[1,2,3,0,2]
a.maxProfit(prices)

3