网站导航自适应,做投资的网站好,网站制作的核心要点是什么,嘉兴网站推广公司Day 46 动态规划 part12 解题理解309714 2道题目 309. 买卖股票的最佳时机含冷冻期 714. 买卖股票的最佳时机含手续费
解题理解
309
这道题不太好理解#xff0c;需要考虑的情况很多并且不好确定。可以设置每天的状态有4种#xff1a; dp[i][0] 今天持有股票 dp[i][1] 今天… Day 46 动态规划 part12 解题理解309714 2道题目 309. 买卖股票的最佳时机含冷冻期 714. 买卖股票的最佳时机含手续费
解题理解
309
这道题不太好理解需要考虑的情况很多并且不好确定。可以设置每天的状态有4种 dp[i][0] 今天持有股票 dp[i][1] 今天保持卖出 dp[i][2] 今天卖出 dp[i][3] 今天冷冻 dp[i][0]可以从以下三种状态得到昨天持有昨天冷冻今天买昨天保持卖出今天买。 dp[i][1]可以从以下两种状态得到昨天保持卖出昨天冷冻 dp[i][2]只能从一种情况得到昨天持有今天卖。 dp[i][3]只能从一种情况得到昨天卖出。 这里需要注意将今天保持卖出和今天卖出作两种情况的考虑这样能让每种情况都可以从前一天的一种情况中递推过来而且还能让今天的冷冻状态只保持一天。
class Solution:def maxProfit(self, prices: List[int]) - int:dp [[0] * 4 for _ in range(len(prices))]# dp[i][0] 今天持有股票# dp[i][1] 今天保持卖出# dp[i][2] 今天卖出# dp[i][3] 今天冷冻dp[0][0] -prices[0]for i in range(1, len(prices)):dp[i][0] max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i])dp[i][1] max(dp[i - 1][1], dp[i - 1][3])dp[i][2] dp[i - 1][0] prices[i]dp[i][3] dp[i - 1][2]return max(dp[-1][3], dp[-1][2], dp[-1][1])714
跟昨天一道题几乎一样只需要对卖出股票时添加手续费即可。
class Solution:def maxProfit(self, prices: List[int], fee: int) - int:n len(prices)dp [[0] * 2 for _ in range(n)]dp[0][0] -prices[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[-1][-1]
