专栏首页木又AI帮打卡群刷题总结0925——最佳买卖股票时机含冷冻期

打卡群刷题总结0925——最佳买卖股票时机含冷冻期

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

链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown

给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 示例: 输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解题:

1、dp问题。每个时刻,都只有三种状况:持有股票、冷冻期、未持有股票。

我们使用三个dp数组分别存储这三种情况的最大利润,分别记为dp_with_buy 、dp_in_cool、dp_not_buy ,那么公式有:

# 未持有:前一时刻未持有股票的最大利润,此时卖出股票的最大利润,两者最大值

dp_not_buy[i] = max(dp_not_buy[i - 1], dp_with_buy[i - 1] + prices[i])

# 持有:前一时刻持有股票的最大利润,此时冷冻结束可以买入的最大利润,两者最大值 dp_with_buy[i] = max(dp_with_buy[i - 1], dp_in_cool[i - 1] - prices[i])

# 冷冻:前一时刻冷冻的最大利润,前一时刻卖出股票的最大利润,两者最大值 dp_in_cool[i] = max(dp_not_buy[i - 1], dp_in_cool[i - 1])

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

PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

PPS:还是得日更呀,总结一下总是好的。

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

    你的益达
  • 309. 最佳买卖股票时机含冷冻期

    设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

    用户7447819
  • ​LeetCode刷题实战309:最佳买卖股票时机含冷冻期

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 【LeetCode】309. 最佳买卖股票时机含冷冻期

    设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

    韩旭051
  • 打卡群刷题总结0917——买卖股票的最佳时机

    链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

    木又AI帮
  • 力扣309——最佳买卖股票时机含冷冻期

    设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

    健程之道
  • 打卡群刷题总结1007——买卖股票的最佳时机 II

    链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii

    木又AI帮
  • 动态规划:本周我们都讲了这些(系列七)

    这也是和121. 买卖股票的最佳时机的唯一区别(注意只有一只股票,所以再次购买前要出售掉之前的股票)

    代码随想录
  • 一个函数解决【LeetCode 买卖股票的最佳时机】系列所有题目!

    之前介绍了【LeetCode 买卖股票的最佳时机】系列一共六道题目,这里把之前的题解还有题目链接汇总一下,方便大家查找。

    lucifer210
  • LeetCode 309. 最佳买卖股票时机含冷冻期(动态规划)

    设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

    Michael阿明
  • 动态规划:买卖股票需要冷静期!

    题目链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-coold...

    代码随想录
  • 每日算法系列【LeetCode 309】最佳买卖股票时机含冷冻期

    设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

    godweiyang
  • LeetCode 全站第一,牛逼!

    本文地址:https://leetcode-cn.com/circle/article/qiAgHn/

    GitHubDaily
  • 股票问题-LeetCode #121、122、309、714、123、188(一解6杀,状态转移)

    dp初始化: dp[-1][k][0] = dp[i][0][0] = 0 dp[-1][k][1] = dp[i][0][1] = -infinity

    算法工程师之路
  • 一天一大 leet(最佳买卖股票时机含冷冻期)难度:中等-Day20200710

    设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

    前端小书童
  • leetcode: explore-array-22 买卖股票的最佳时机 II

    leetcode explore 初级算法第二题:买卖股票的最佳时机 II。这个系列目前一共有5道题目:

    用户7685359
  • 【LeetCode】贪心算法--买卖股票的最佳时机 II(122)

    为什么要在LeetCode刷题?大家都知道不管是校招还是社招算法题是必考题,而这一部分恰巧是大多数人的短板,所以刷题首先是为了提高自身的编程能力,能够在算法面试...

    PM小王
  • 贪心算法:买卖股票的最佳时机II

    题目链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

    代码随想录
  • 【小Y学算法】⚡️每日LeetCode打卡⚡️——35. 买卖股票的最佳时机

    给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

    呆呆敲代码的小Y

扫码关注云+社区

领取腾讯云代金券