123. 买卖股票的最佳时机 III
题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
0x1 看到题目的第一想法
0x2 自己实现过程中遇到哪些困难
0x3 今日学习的文章链接，或者视频链接
0x4 看完代码随想录之后的想法
- 全程可以最多买卖两次
- 一共5种状态
# dp[i][0] 没有操作 从来没买 # dp[i][1] 表示第i天第一次持有股票所得最多现金 # 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
188.买卖股票的最佳时机IV
题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
0x1 看到题目的第一想法
0x2 自己实现过程中遇到哪些困难
0x3 今日学习的文章链接，或者视频链接
0x4 看完代码随想录之后的想法
- 类比123
- 最多k次交易，则每天有2k+1种状态
0x5 今日收获，记录一下自己的学习时长
- 1h
总结
- 动态规划
- 买卖股票
- 两种状态，持有or不持有
- 买卖股票
复习
- day25
- 回溯
- 组合问题
- path, res
- startIdx
- 回溯
待重点复习
123, 188