【刷题DAY51】309, 714.md

发表于 | 分类于

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

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 分析状态
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    # 四种状态
    # 0. 持有 1. 不持有(保持卖出状态) 3. 今天卖出 4. 冷冻期

    # 0. 持有
    # 前一天持有，保持 dp[i-1][0]
    # 今天买入，前一天冷冻 or 前一天不持有 
    # dp[i-1][3] - prices[i] or dp[i-1][1] - prices[i]
    # dp[i] = max(dp[i-1][0], dp[i-1][3] - prices[i], dp[i-1][1] - prices[i])
    # 1. 不持有
    # 前一天是不持有状态 dp[i-1][1]
    # 前一天是冷冻期    dp[i-1][3]
    # dp[i][1] = max(dp[i-1][1], dp[i-1][3)]
    # 2. 今天卖出
    # 前一天一定是持有状态 
    # dp[i][2] = dp[i-1][0] + prices[i]
    # 3. 冷冻期
    # 前一天一定买卖了
    # dp[i][3] = dp[i-1][2]

    # 初始化
    # dp[0][0] = -prices[0]
    # dp[0][1] = 0
    # dp[0][2] = 1
    # dp[0][3] = 1

0x5 今日收获，记录一下自己的学习时长

  • 1h

714. 买卖股票的最佳时机含手续费

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

  • 漏

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 类比122，多了手续费

0x5 今日收获，记录一下自己的学习时长

  • 1h

总结

  • 动态规划
    • 股票问题
      • 买卖股票的最佳时机(买卖一次)(两种状态)
      • 买卖股票的最佳时机II(买卖多次)(两种状态)
      • 买卖股票的最佳时机III(最多买卖两次)(5种状态)
      • 买卖股票的最佳时机IV(最多买卖k次)(2k+1种状态)
      • 多次买卖股票+冷冻期(4种状态)
      • 多次买卖股票+手续费(两种状态)

复习

  • day27
    • 回溯
      • 分割问题
      • 子集问题
        • 遍历整棵树

待重点复习

309