首页 > 编程语言 >代码随想录算法训练营第43天 | 动态规划7:买卖股票

代码随想录算法训练营第43天 | 动态规划7:买卖股票

时间:2024-07-25 10:51:52浏览次数:18  
标签:买卖 max 训练营 随想录 43 最佳时机 股票 prices dp

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])

标签:买卖,max,训练营,随想录,43,最佳时机,股票,prices,dp
From: https://www.cnblogs.com/P201821440041/p/18321060

相关文章