Leetcode Day18 股票买卖专题

本文主要是介绍Leetcode Day18 股票买卖专题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

买卖股票重要的部分就是状态转移, 通常是二维i,0/1代表第i天持有/不持有股票时的最大利润

Part 1: 不限制交易次数

122 每天都可买入卖出

class Solution:def maxProfit(self, prices: List[int]) -> int:# on day i, we have stockdp1 = [0] * len(prices)# on day i, we dont have stockdp2 = [0] * len(prices)dp1[0] = -prices[0] for i in range(1, len(prices)):# 有 stock, 什么都不做 -> dp1# 无 stock ,什么都不做 -> dp2# 有stock卖了 -> dp2# 无stock, 买了 -> dp1dp1[i] = max(dp1[i-1], dp2[i-1] - prices[i])dp2[i] = max(dp2[i-1], dp1[i-1] + prices[i])return max(dp1 + dp2)

309 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)

只需改为dp1[i] = max(dp1[i-1], dp2[i-2] - prices[i]), 因为dp1[i]的第二部分代表买入, 买入的话必须是i-2的那一天没有股票

Part 2: 有交易限制

121 (一次) 一天买入, 未来一天卖出

反着遍历记录后缀最大即可

class Solution:def maxProfit(self, prices: List[int]) -> int:max_price = -1ans = -1for i in range(len(prices) - 1,-1, -1):if prices[i] > max_price:max_price = prices[i]ans = max(ans, max_price - prices[i])return ans 

123 (两次)

class Solution:def maxProfit(self, prices: List[int]) -> int:n = len(prices)# dp[i][j]: 第i天结束后的最大利润，j的含义如下：# 0: 第一次买入, 1: 第一次卖出, 2: 第二次买入, 3: 第二次卖出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], prices[i] + dp[i-1][0])# 第二次买入：保持前一天状态，或今天买入（使用第一次卖出的利润）dp[i][2] = max(dp[i-1][2], -prices[i] + dp[i-1][1])# 第二次卖出：保持前一天状态，或今天卖出dp[i][3] = max(dp[i-1][3], prices[i] + dp[i-1][2])return dp[-1][-1]  # 返回最后一天第二次卖出的最大利润

188 最多k次

class Solution:def maxProfit(self, k: int, prices: List[int]) -> int:if not prices or k == 0:return 0n = len(prices)# dp1[i][j] -> 第i天持有股票, 已经完成j次交易# dp2[i][j] -> 第i天没有股票, 已经完成j次交易dp1 = [[0 for _ in range(k + 1)] for _ in range(n)]dp2 = [[0 for _ in range(k + 1)] for _ in range(n)]# 初始化第一天的状态dp1[0][0] = -prices[0]# 初始化第一次交易的状态for i in range(1, n):dp1[i][0] = -prices[i]for i in range(1, n):for j in range(1, k + 1):# 持有股票的状态dp1[i][j] = max(dp1[i-1][j], dp2[i-1][j] - prices[i])# 不持有股票的状态dp2[i][j] = max(dp2[i-1][j], dp1[i-1][j-1] + prices[i])return max(dp2[-1])

代码基本上是正确的, 但是在初始化出了问题, 对于dp[i][0],不能全部初始化为-pirces[0], 因为第0天后可能会出现更低的价格

class Solution:def maxProfit(self, k: int, prices: List[int]) -> int:if not prices or k == 0:return 0n = len(prices)# dp1[i][j] -> 第i天持有股票, 已经完成j次交易# dp2[i][j] -> 第i天没有股票, 已经完成j次交易dp1 = [[-inf for _ in range(k + 1)] for _ in range(n)]dp2 = [[-inf for _ in range(k + 1)] for _ in range(n)]# 初始化第一天的状态cur_max = -inffor i in range(n):if -prices[i] > cur_max:cur_max = -prices[i]dp1[i][0] = cur_maxfor i in range(1, n):for j in range(1, k + 1):# 持有股票的状态dp1[i][j] = max(dp1[i-1][j], dp2[i-1][j] - prices[i])# 不持有股票的状态dp2[i][j] = max(dp2[i-1][j], dp1[i-1][j-1] + prices[i])return max(dp2[-1])

注意dp[i][0]的初始化, 和所有的初始最大利润应该为-inf

这篇关于Leetcode Day18 股票买卖专题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---