当前位置: 首页 > news >正文

代码随想录算法训练营第四十八天| LeetCode121. 买卖股票的最佳时机、122.买卖股票的最佳时机II、123.买卖股票的最佳时机III

121. 买卖股票的最佳时机

题目描述: 121. 买卖股票的最佳时机.

解法

dp

class Solution(object):def maxProfit(self, prices):if not prices:return 0dp0 = 0# 0表示不持有股票,1表示持有股票dp1 = 0-prices[0]for i in range(1,len(prices)):# 当前没有股票# 两种情况,前一天也没有,前一天的有但今天卖了dp0 = max(dp0,dp1+prices[i])# 当前有股票,昨天就有今天没卖,之前没有今天买了dp1 = max(dp1,0-prices[i])return dp0

这个题是只能买一次然后卖一次,只有一次机会。
可以使用两个变量来代替这个

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

题目描述: 122.买卖股票的最佳时机II.

解法

dp

class Solution(object):def maxProfit(self, prices):dp0 = 0dp1 = -prices[0]for i in range(len(prices)):tmp = dp0dp0 = max(dp0,dp1+prices[i])dp1 = max(dp1,tmp-prices[i])return dp0

这个是随时买随时卖。

123.买卖股票的最佳时机III

题目描述: 123.买卖股票的最佳时机III.

解法

dp

class Solution(object):def maxProfit(self, prices):#0代表没有,1代表有第一支,2代表卖了第一支的没有,3代表有第二支,4代表第二支卖了。dp = [[0]*5 for _ in range(len(prices))]dp[0][1] = -prices[0]dp[0][2] = 0dp[0][3] = -prices[0]dp[0][4] = 0for i in range(1,len(prices)):dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i])dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i])dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i])return max(dp[len(prices)-1][0],dp[len(prices)-1][2],dp[len(prices)-1][4])

用多维数组表示状态。

http://www.lryc.cn/news/162451.html

相关文章:

  • C++新经典10--vector以及其使用
  • std : : vector
  • AJAX学习笔记8 跨域问题及解决方案
  • webhook--详解(gitee 推送)
  • 高速路自动驾驶功能HWP功能定义
  • Leetcode113. 路径总和 II
  • 分布式锁之redis实现
  • Idea中如何在一个项目中引入其他子模块?
  • UDP协议概述
  • Python-tracemalloc-跟踪内存分配
  • 02 CSS技巧
  • Yarn资源调度器
  • android上架备案公钥和md5获取工具
  • SpringBoot系列(12):SpringBoot集成log4j2日志配置
  • HTML事件列表
  • 并发-Executor框架笔记
  • 【C进阶】分析 C/C++程序的内存开辟与柔性数组(内有干货)
  • 深入理解 JVM 之——字节码指令与执行引擎
  • C++:vector
  • Android Automotive编译
  • 什么是50ETF期权开户条件,怎么开期权交易权限?
  • React 从入门到精通——本文来自AI创作助手
  • 【51单片机实验笔记】前篇(三) 模块功能封装汇总(持续更新)
  • Excel VSTO开发4 -其他事件
  • 语音识别数据的采集方法:基本流程数据类型
  • oracle数据库给用户授权DBA权限Oracle查看哪些用户具有DBA权限
  • 024-从零搭建微服务-系统服务(六)
  • Arduino驱动TCS3200传感器(颜色传感器篇)
  • 基于Matlab实现多个数字水印案例(附上源码+数据集)
  • C语言之指针进阶篇(2)