当前位置：首页 > article >正文

Day 46 动态规划 part12

article 2024/9/24 3:29:50

Day 46 动态规划 part12

解题理解
- 309
- 714

2道题目
309. 买卖股票的最佳时机含冷冻期
714. 买卖股票的最佳时机含手续费

解题理解

309

这道题不太好理解，需要考虑的情况很多并且不好确定。可以设置每天的状态有4种：
dp[i][0] 今天持有股票
dp[i][1] 今天保持卖出
dp[i][2] 今天卖出
dp[i][3] 今天冷冻
dp[i][0]可以从以下三种状态得到：昨天持有，昨天冷冻今天买，昨天保持卖出今天买。
dp[i][1]可以从以下两种状态得到：昨天保持卖出，昨天冷冻
dp[i][2]只能从一种情况得到：昨天持有今天卖。
dp[i][3]只能从一种情况得到：昨天卖出。
这里需要注意将今天保持卖出和今天卖出作两种情况的考虑，这样能让每种情况都可以从前一天的一种情况中递推过来，而且还能让今天的冷冻状态只保持一天。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[0] * 4 for _ in range(len(prices))]
        # dp[i][0] 今天持有股票
        # dp[i][1] 今天保持卖出
        # dp[i][2] 今天卖出
        # dp[i][3] 今天冷冻
        dp[0][0] = -prices[0]
        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][3])
            dp[i][2] = dp[i - 1][0] + prices[i]
            dp[i][3] = dp[i - 1][2]
        return max(dp[-1][3], dp[-1][2], dp[-1][1])

714

跟昨天一道题几乎一样，只需要对卖出股票时添加手续费即可。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = -prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee)
        return dp[-1][-1]