<代码随想录> 算法训练营-2024.12.23

news/2024/12/28 3:38:24/

今日专题 动态规划 股票买卖

今日总结:动态规划得好好想一想需要什么状态,状态其实是用来描述子问题的

121. 买卖股票的最佳时机

解法一:动态规划

class Solution:def maxProfit(self, prices: List[int]) -> int:#dp[i][j] 表示当前拥有的钱 i表示天数,j表示第i天是否还持有这只股票 j取值0或1size=len(prices)dp=[[0]*2 for _ in range(size)]dp[0][1]=-prices[0]for i in range(1,size):dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1]=max(dp[i-1][1],-prices[i])return dp[-1][0]

解法二:贪心解法

class Solution:def maxProfit(self, prices: List[int]) -> int:res=0min_price=prices[0]for p in prices:res=max(res,p-min_price)min_price=min(p,min_price)return res
122. 买卖股票的最佳时机 II

解法一:动态规划解法

class Solution:def maxProfit(self, prices: List[int]) -> int:#dp[i][j] 表示当前拥有的钱 i表示天数,j表示第i天是否还持有这只股票 j取值0或1size=len(prices)dp=[[0]*2 for _ in range(size)]dp[0][1]=-prices[0]for i in range(1,size):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[-1][0]

解法二:贪心解法

class Solution:def maxProfit(self, prices: List[int]) -> int:#相邻的两天,如果后一天比前一天高,则可以在前一天买后一天卖res=0temp=10**4+1for price in prices:if price-temp>0:res+=price-temptemp=pricereturn res
123. 买卖股票的最佳时机 III
class Solution:def maxProfit(self, prices: List[int]) -> int:# dp[i][j][k] i表示天数 j表示是否持有股票 k表示完成交易数size = len(prices)dp = [[[0 for _ in range(3)] for _ in range(2)] for _ in range(size)]dp[0][1][0] = -prices[0]dp[0][1][1] = -prices[0]for i in range(1, size):# 不持有可能是前一天不持有(交易0/1/2)或者前一天持有(0/1)dp[i][0][2] = max(dp[i - 1][0][2], dp[i - 1][1][1] + prices[i])dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][1][0] + prices[i])dp[i][0][0] = dp[i - 1][0][0]# 当天持有 可能是当天买的,前一天(0/1),或者前一天就有的(0/1)dp[i][1][0] = max(dp[i - 1][1][0], -prices[i])dp[i][1][1] = max(dp[i - 1][0][1] - prices[i], dp[i - 1][1][1])return max(dp[-1][0][0], dp[-1][0][1], dp[-1][0][2])

http://www.ppmy.cn/news/1558683.html

相关文章

华为云语音交互SIS的使用案例(文字转语音-详细教程)

文章目录 题记一 、语音交互服务(Speech Interaction Service,简称SIS)二、功能介绍1、实时语音识别2、一句话识别3、录音文件识别4、语音合成 三、约束与限制四、使用1、API2、SDK 五、项目集成1、引入pom依赖2、初始化 Client1)…

Grok 2.0:马斯克的大模型挑战ChatGPT,AI竞争再升级

引言:马斯克Grok 2.0的横空出世 在人工智能(AI)领域,竞争从未停止。随着大型语言模型(LLM)的快速发展,各大科技巨头纷纷推出自己的AI模型,试图在激烈的竞争中占据领先地位。最近&am…

shell学习简介(一)

这里写目录标题 一、Shell简介二、Shell脚本注意事项三、入门脚本 一、Shell简介 Shell 脚本是一种用于自动化任务的脚本语言,通常在 Unix/Linux 系统中使用。通过结合条件判断和循环来实现命令的自动运行以完成一些相对固定的操作。 简单说:Shell就是一…

golang 指针demo

我根据实战经验总结了以下几点使用指针的建议,供你参考: 不要对 map、slice、channel 这类引用类型使用指针; 如果需要修改方法接收者内部的数据或者状态时,需要使用指针; 如果需要修改参数的值或者内部数据时&#x…

云开发 Copilot:AI 赋能的低代码革命

云开发 Copilot:AI 赋能的低代码革命 目录: 一、引言:AI 时代的开发新纪元 1.1 低代码与AI的完美融合1.2 云开发 Copilot的革命性意义 二、云开发 Copilot 的核心特性解析 2.1 快速生成应用功能2.2 低代码与AI的深度结合 三、实战演练&…

网络安全加密

介绍 一个认证和密钥交换系统,它用来在不可靠的网络中保护口令和交换密钥。通过消除了在网络上发送明文口令的需要,并且通过安全的密钥交换机制来使用加密,改进了安全性。服务器不保存密码或密码的散列值, 防止字典攻击. 而只是保存验证因子(…

aws(学习笔记第十九课) 使用ECS和Fargate进行容器开发

aws(学习笔记第十九课) 使用ECS和Fargate进行容器开发 学习内容: 使用本地EC2中部署docker应用使用ECS的EC2模式进行容器开发使用ECS的Fargate模式进行容器开发 1. 使用本地EC2中部署docker应用 docker整体 这里展示了docker的整体流程。 开发阶段 编写dockerfile…

Kibana安装教程——Linux

Kibana安装教程——Linux 一、安装 下载安装包: 官网下载地址:https://www.elastic.co/cn/downloads/kibana 上传包到linux 切换到安装目录下 解压:tar -zxvf kibana-7.17.1-linux-x86_64.tar.gz 重命名安装文件夹 mv kibana-7.17.1-linux-x…