最佳买卖股票时机含冷冻期

Leetcode Link: 309. 最佳买卖股票时机含冷冻期 - 力扣（LeetCode）

题目

给定一个整数数组 prices，其中第  prices[i] 表示第 i 天的股票价格。

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

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

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

解法一

从暴力递归到动态规划

暴力递归

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        @functools.lru_cache()
        def process (state, i):
	        # state-持有状态 i-第i天
            if i>= len(prices): # >= 主要因为有 i+2
                return 0
            if state == 0:
                p1 = process(0, i+1)
                p2 = process(1, i+1) - prices[i]
            else:
                p1 = process(1, i+1)
                p2 = process(0, i+2) + prices[i]
            return max(p1,p2)
            
        return process(0, 0)

动态规划

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # [state, i]
        dp = [[0 for _ in range(len(prices)+1)] for _ in range(2)]
 
        for i in range(len(prices)-1, -1, -1):
            dp[0][i] = max(dp[0][i+1], dp[1][i+1]-prices[i])
            
            if i + 2 <= len(prices):
                dp[1][i] = max(dp[1][i+1], dp[0][i+2]+prices[i])
            else:
                dp[1][i] = max(dp[1][i+1], prices[i])
        return dp[0][0]

注意更新dp表的时候，当i+2越界时，dp[1][i]的值是什么

不是直接等于dp[1][i+1]的！是需要把今天卖出的钱算上的！看代码！刚开始直接写成了

if i + 2 <= len(prices):
    dp[1][i] = max(dp[1][i+1], dp[0][i+2]+prices[i])
else:
    dp[1][i] = dp[1][i+1]  # 这里不对

启发和联系

当暴力递归的 base case 不只有 == 时候，变成 dp 的时候需要考虑边界的返回值，结合边界溢出哪一个子函数的父函数来考虑！

或者说，直接看暴力递归中，当有一个情况边界溢出的时候，我们还考不考虑这种情况的返回值，如果直接没有这种情况，那么就好说了，直接少一种情况。如果还是有这种情况的，那么就要考虑上一层中，该情况的结果是多少。