121.买卖股票的最佳时机
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
代码随想录
https://programmercarl.com/0121.买卖股票的最佳时机.html#算法公开课and-sell-stock/description/
122.买卖股票的最佳时机II
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
代码随想录
https://programmercarl.com/0122.买卖股票的最佳时机II(动态规划).html
123.买卖股票的最佳时机III
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
代码随想录
https://programmercarl.com/0123.买卖股票的最佳时机III.html#算法公开课
121. 买卖股票的最佳时机
题解思路
- dp含义:dp[i] = dp[i][0] dp[i][1]
-dp[i][0]:第i只股票没买的状态;
-dp[i][1]:第i只股票买了的状态; - dp递推
dp[i][0] = max(dp[i-1][0] (什么也没做,本身就没有),dp[i-1][1]+prices[i](原本持有的股票卖了) )
dp[i][1] = max(dp[i-1][1] (什么也没做,本身就有),-price[i] (买股票) ) - 初始化
- dp[0][1] = -prices[0] 买了股票1
题解代码
点击查看代码
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = [[0]*2]*2
dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1,len(prices)):
dp[1][0] = max(dp[0][0],dp[0][1]+prices[i])
dp[1][1] = max(dp[0][1],-prices[i])
dp[0] = dp[1]
return dp[1][0]
122.买卖股票的最佳时机II
题解思路
- 在1的基础上 增加一个买卖次数即可
题解代码
点击查看代码
```python class Solution: def maxProfit(self, prices: List[int]) -> int: dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1,len(prices)):
dp[1][0] = max(dp[0][0],dp[0][1]+prices[i])
dp[1][1] = max(dp[0][1],dp[0][0]-prices[i])
dp[0] = dp[1]
return dp[0][0]
</details>
# 123.买卖股票的最佳时机III
## 解题思路
- dp有4个状态:
| dp[i][j] | 含义 | 初始化 | 递推公式 |对应动作|
|:--------:| :-------------:|:---------:|:--------------:|:--------------:|
|dp[i][0]|第i个股票内未完成任何动作|0|dp[i-1][0]|什么动作都没做|
|dp[i][1]|第i个股票内第1次买入|-prices[0]|max(dp[i-1][1],dp[i-1][0]-prices[i])|(None,买1)
|dp[i][2]|第i个股票内第1次卖出|0|max(dp[i-1][2],dp[i-1][1]+prices[i])|(None,卖1)
|dp[1][3]|第i个股票内第2次买入|-prices[0]|max(dp[i-1][3],dp[i-1][3]-prices[i])|(None,买2)|
|dp[1][4]|第i个股票内第2次卖出|0|max(dp[i-1][4],dp[i-1][3]+prices[i])|(None,卖2)
- dp按照状态转移计算即可
<details>
<summary>点击查看代码</summary>
```python3
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = [[0]*5]*2
dp[0][0] = 0
dp[0][1] = -prices[0]
dp[0][2] = 0
dp[0][3] = -prices[0]
dp[0][4] = 0
for i in range(1,len(prices)):
dp[1][0] = dp[0][0]
dp[1][1] = max(dp[0][1],dp[0][0]-prices[i])
dp[1][2] = max(dp[0][2],dp[0][1]+prices[i])
dp[1][3] = max(dp[0][3],dp[0][2]-prices[i])
dp[1][4] = max(dp[0][4],dp[0][3]+prices[i])
dp[0] = dp[1]
return max(dp[1])