第九章 动态规划part10

这篇具有很好参考价值的文章主要介绍了第九章 动态规划part10。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

121. 买卖股票的最佳时机

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

122. 买卖股票的最佳时机 II

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[0]*2 for _ in range(len(prices))]
        dp[0][0] = -prices[0]
        for i in range(1,len(prices)):
            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])
        return dp[len(prices)-1][1]

分多次购买和一次购买的区别文章来源地址https://www.toymoban.com/news/detail-846242.html

到了这里,关于第九章 动态规划part10的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode题目详解】第九章 动态规划part06 完全背的讲解 518. 零钱兑换 II 377. 组合总和 Ⅳ (day44补)

    # 完全背包 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 每件物品都有无限个(也就是可以放入背包多次) ,求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件 。

    2024年02月09日
    浏览(38)
  • 第九章 动态规划part04(● 01背包问题,你该了解这些! ● 01背包问题,你该了解这些! 滚动数组 ● 416. 分割等和子集 )

    ● 01背包问题,你该了解这些! ● 01背包问题,你该了解这些! 滚动数组 ● 416. 分割等和子集 https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html 视频讲解:https://www.bilibili.com/video/BV1cg411g7Y6 1.确定dp数组以及下标的含义 i是物品,j是背包容量

    2024年01月16日
    浏览(52)
  • 【LeetCode题目详解】第九章 动态规划part09 198.打家劫舍 213.打家劫舍II 337.打家劫舍III(day48补)

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动

    2024年02月09日
    浏览(46)
  • 算法训练day49|动态规划part10

    贪心 因为股票就买卖一次,那么贪心的想法很自然就是取最左最小值,取最右最大值,那么得到的差值就是最大利润。 本次重点学习动态规划方法 1. dp数组(dp table)以及下标的含义 dp[i][0] 表示第i天持有股票所得最多现金,一开始现金为负数,所以第一天就持有股票的话,

    2024年02月03日
    浏览(46)
  • 第九章动态规划——不同路径(二)有障碍物

    目录 力扣题号:63. 不同路径 II - 力扣(LeetCode) 题目描述 示例 提示 思路 解法一:动态规划 (1)dp数组的下标及其含义 (2)确定递推公式 (3)初始化递推数组 (4)确定遍历顺序 (5)根据题意推出dp数组对照 障碍物处理 代码实现 总结 注:下述题目描述和示例均来自力

    2024年04月23日
    浏览(37)
  • day55 算法训练|动态规划part15

    给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,\\\"ace\\\"是\\\"abcde\\\"的一个子序列,而\\\"aec\\\"不是)。 其实就是最长公共子序列的变种题:如果公共子序列长度等于

    2024年02月02日
    浏览(63)
  • day48算法训练|动态规划part09

    1. dp数组(dp table)以及下标的含义 dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i] 。 2.递推公式 决定dp[i]的因素就是第i房间偷还是不偷。 如果偷第i房间,那么dp[i] = dp[i - 2] + nums[i] ,即:第i-1房一定是不考虑的,找出 下标i-2(包括i-2)以内的房屋,最多

    2024年01月16日
    浏览(42)
  • day52 算法训练|动态规划part13

    参考:代码随想录 1. dp[i]的定义 本题中,正确定义dp数组的含义十分重要。 dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度 为什么一定表示 “以nums[i]结尾的最长递增子序” ,因为我们在 做 递增比较的时候, 如果比较 nums[j] 和 nums[i] 的大小,那么两个递增子序列

    2024年01月15日
    浏览(41)
  • 代码随想录算法训练51 | 动态规划part12

    本题加了一个冷冻期,状态就多了,有点难度,大家要把各个状态分清,思路才能清晰  视频讲解: 动态规划来决定最佳时机,这次有冷冻期!| LeetCode:309.买卖股票的最佳时机含冷冻期_哔哩哔哩_bilibili 代码随想录 相对122.买卖股票的最佳时机II ,本题只需要在计算卖出操

    2024年01月18日
    浏览(55)
  • 【Day53】代码随想录之动态规划part10——买卖股票的最佳时机、买卖股票的最佳时机II

    昨天已经把打家劫舍的问题解决了,最后一个题目涉及到树形dp比较难(等到二刷的时候再重点看下),今天的任务是解决股票问题。 今日任务: 121.买卖股票的最佳时机 122.买卖股票的最佳时机II Leetcode题目:【121.买卖股票的最佳时机】 因为此题中买卖股票只能买卖一次。

    2024年03月15日
    浏览(96)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包