Day 46 动态规划 part12

本文主要是介绍Day 46 动态规划 part12，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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]

这篇关于Day 46 动态规划 part12的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---