【刷题DAY50】复习.md

发表于 | 分类于

123. 买卖股票的最佳时机 III

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

天第一次持有股票所得最多现金

    # dp[i][2] 表示第i天第一次不持有股票所得最多现金
    # dp[i][3] 表示第i天第二次持有股票所得最多现金
    # dp[i][4] 表示第i天第二次不持有股票所得最多现金

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
        # 动态规划
# 1. 
# dp[i][0] 没有操作 从来没
# dp[i][1] 表示第i天第一次持有股票所得最多现金
# dp[i][2] 表示第i天第一次不持有股票所得最多现金
# dp[i][3] 表示第i天第二次持有股票所得最多现金
# dp[i][4] 表示第i天第二次不持有股票所得最多现金
# 2. dp[i][1]第i天第一次持有股票
# 操作一：第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天第一次不持有股票
# 操作一：第i-1天就第一次不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][2]
# 操作二：第i天第一次卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][1]
# dp[i][2] = max(dp[i-1][2], prices[i] + dp[i - 1][1])
# dp[i][3] 表示第i天第二次持有股票所得最多现金
# 操作一：第i-1天就第二次持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][3]
# 操作二： 第i天第二次买入股票，所得现金就是买入今天的股票后所得现金即：dp[i-1][2]-prices[i]
# dp[i][3] = max(dp[i-1][2] - prices[i], dp[i - 1][3])
# dp[i][4]第i天第二次不持有股票
# 操作一： 第i-1天就第二次不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][4]
# 操作二： 第i天第二次卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][3]
# 3. 
# dp[0][1] 表示第0天第一次持有股票的现金 = -prices[0]
# dp[0][2] 表示第0天不持有股票的现金 = 0    当天买当天卖
# dp[0][3] = -prices[0]      
# dp[0][4] = 0

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

  • 1h
  • day25
    • 组合总和III
      • 数字用一次 相加之和为k
    • 电话号码的字母组合
      • 不同集合间的组合问题
      • 没有startIdx
  • day26
    • 组合总和
      • 元素可以重复用
      • startIdx那里 i 不加1就实现了重复取元素的操作
    • 组合总和II
      • 集合里有重复元素，题目要求不能有重复组合
      • 数组必须有序，方能方便的去重
    • 分割回文串
      • 分割问题
      • 终止条件的判断

总结

  • 回溯
    • 组合问题
    • 分割问题
      • 类似组合问题

待重点复习

123, 188