您现在的位置是：首页 >学无止境 >【LeetCode 刷题】动态规划(4)-股票问题网站首页学无止境

此博客为《代码随想录》动态规划章节的学习笔记，主要内容为动态规划股票问题的相关题目解析。

文章目录

• 121. 买卖股票的最佳时机
• 122. 买卖股票的最佳时机II
• 123. 买卖股票的最佳时机III
• 188. 买卖股票的最佳时机IV
• 309. 最佳买卖股票时机含冷冻期
• 714. 买卖股票的最佳时机含手续费

121. 买卖股票的最佳时机

题目链接

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        # 0 持有 1 未持有
        dp = [[0, 0] for _ in range(n)]
        dp[0] = [-prices[0], 0]
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], -prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
        return dp[n-1][1]

• 股票只能买卖一次
• 状态定义：dp[i][0] 表示第 i 天持有股票所能获得的最多现金；dp[i][1] 表示第 i 天不持有股票所能获得的最多现金
• 状态转移：
  • dp[i][0] = max(dp[i-1][0], -prices[i])，注意：由于股票只能买卖一次，因此当从不持有转换为持有时，一定是第一次持有，之前没有任何交易（现金为 0），持有后即为 -prices[i]；不能为 dp[i-1][1] - prices[i]，因为 dp[i-1][1] 可能包括了之前的交易
  • dp[i][0] = max(dp[i-1][0], -prices[i])
• 返回值：返回不持有股票的最多现金

122. 买卖股票的最佳时机II

题目链接

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        # 0 持有 1 不持有
        dp = [[0, 0] for _ in range(n)]
        dp[0] = [-prices[0], 0]
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
        return dp[n-1][1]

• 股票可以买卖多次
• 与上题唯一不同点为持有股票的递推公式：dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])

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

题目链接

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        # 0 第一次持有 1 第一次不持有..
        dp = [[0, 0, 0, 0] for _ in range(n)]
        dp[0] = [-prices[0], 0, -prices[0], 0]
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], -prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
            dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i])
            dp[i][3] = max(dp[i-1][3], dp[i-1][2] + prices[i])
        return max(dp[n-1][1], dp[n-1][3])

• 股票最多可以买卖两次
• 状态定义：每允许一次交易，定义两个状态，因此共 4 个状态

188. 买卖股票的最佳时机IV

题目链接

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0 for _ in range(2 * k)] for _ in range(n)]
        for i in range(0, 2 * k, 2):
            dp[0][i] = -prices[0]
        for i in range(1, n):
            for j in range(2 * k):
                sig = 1 if j % 2 == 1 else -1
                if j == 0:
                    dp[i][0] = max(dp[i-1][0], -prices[i])
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + sig * prices[i])
        return max([dp[n-1][i] for i in range(1, 2 * k, 2)])

• 股票最多可以买卖 k 次
• 状态定义：每允许一次交易，定义两个状态，因此共 2 * k 个状态

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

题目链接

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        # 0 持有 1 未持有 2 冷冻期
        dp = [[0, 0, 0] for _ in range(n)]
        dp[0] = [-prices[0], 0, 0]
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][2])
            dp[i][2] = max(dp[i-1][2], dp[i-1][0] + prices[i])
        return max(dp[n-1][1], dp[n-1][2])

• 股票可以买卖多次，含冷冻期（1天）
• 状态定义：dp[i][2] 表示第 i 天之后进入冷冻期，第 i+1 天无法买股票
• 递推公式：
  • dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) 未持有状态转移到持有状态
  • dp[i][1] = max(dp[i-1][1], dp[i-1][2])，未持有状态不能直接从持有状态转移，而需要从冷冻期状态转移
  • dp[i][2] = max(dp[i-1][2], dp[i-1][0] + prices[i])，持有状态下，卖出股票，转移到冷冻期状态

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

题目链接

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        # 0 持有 1 未持有
        dp = [[0, 0] for _ in range(n)]
        dp[0] = [-prices[0], 0]
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
        return dp[n-1][1]

• 股票可以买卖多次，含手续费
• 状态转移：
  • dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) 买股票时正常买
  • dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee) 卖股票时扣除手续费