动态规划12 | ● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费 ●总结

本文主要是介绍动态规划12 | ● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费 ●总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

视频讲解：https://www.bilibili.com/video/BV1rP4y1D7ku

https://programmercarl.com/0309.%E6%9C%80%E4%BD%B3%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E6%97%B6%E6%9C%BA%E5%90%AB%E5%86%B7%E5%86%BB%E6%9C%9F.html

• 考点
  • 动态规划
  • 股票问题
• 我的思路
  • 一开始考虑分3个状态，持有股票、不持有股票（前一天刚卖）、不持有股票（卖了超过一天），写代码的过程中发现后面两个状态可以合并为一个状态不持有股票
  • 递推公式
    • 持有股票的状态，可以由两种情况取较大者推得：前一天持有股票的dp值，两天之前不持有股票的dp值减去今天买入股票的价格
    • 不持有股票的状态，可以由两种情况取较大者推得：前一天不持有股票的dp值，前一天持有股票的dp值加上今天卖出股票的价格
  • 最后的返回值为最后一天两种状态里的较大者
• 视频讲解关键点总结
  • 和我的一致
• 我的思路的问题
  • 无
• 代码书写问题
  • 无
• 可执行代码

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

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

视频讲解：https://www.bilibili.com/video/BV1z44y1Z7UR
https://programmercarl.com/0714.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA%E5%90%AB%E6%89%8B%E7%BB%AD%E8%B4%B9%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html

• 考点
  • 动态规划
  • 股票买卖
• 我的思路
  • 本题其实就是在最基础的股票买卖上加了一个手续费，只要在每次买入股票的同时把手续费算上即可
• 视频讲解关键点总结
  • 思路一致
• 我的思路的问题
  • 无
• 代码书写问题
  • 无
• 可执行代码

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

总结

• 见我的另一篇文章

这篇关于动态规划12 | ● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费 ●总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---