Day50代码随想录动态规划part12:309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费
Day50 动态规划part12 股票问题
309.最佳买卖股票时机含冷冻期
leetcode题目链接:309. 买卖股票的最佳时机含冷冻期 - 力扣(LeetCode)
题意:给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
- 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
- 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
思路:
- dp数组含义:第i天的状态
- dp[i][0]是持有股票的状态
- dp[i][1]是保持卖出股票的状态(冷冻期之后)
- dp[i][2]是卖出股票的操作(之前dp[i][1]和dp[i][2]是归为一类的)
- dp[i][3]冷冻期
- 递推公式:
- 如果在第i天持入dp[i][0]:dp[i][0]=max(dp[i-1][0]前一天就持有, 冷冻期的下一天持有dp[i-1][3]-prices[i],也可以是冷冻期之后一直没有操作,一直是保持卖出股票的状态dp[i-1][1]-prices[i])
- dp[i][1] = max(dp[i-1][1]前一题就保持卖出, dp[i-1][3]前一题是冷冻期)
- dp[i][2] = dp[i-1][0] + prices[i]
- dp[i][3] = dp[i-1][2]前一题一定是卖出的状态
- 初始化:基础是di0天,dp[0][0] = -prices[0], dp[0][1] =0 (本来是不合理的状态,所以要考虑递推公式里dp[i][0] = dp[i-1][1]- price[i]这一项,需要初始化成多少就写成多少),dp[0][2] = 0, dp[0][3] = 0
- 遍历顺序:从小到大遍历
class Solution:def maxProfit(self, prices: List[int]) -> int:dp = [[0]*4 for i in range(len(prices))]# 初始化dp[0][0] = -prices[0]dp[0][1] = 0dp[0][2] = 0dp[0][3] = 0for i in range(1, len(prices)):dp[i][0] = max(dp[i-1][0], dp[i-1][3]-prices[i], dp[i-1][1]-prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][3])dp[i][2] = dp[i-1][0] + prices[i]dp[i][3] = dp[i-1][2]return max(dp[len(prices)-1][1], dp[len(prices)-1][2], dp[len(prices)-1][3])
714.买卖股票的最佳时机含手续费
leetcode题目链接:. - 力扣(LeetCode)
题意:给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。
注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。
class Solution:def maxProfit(self, prices: List[int], fee: int) -> int:dp = [[0]*2 for i in range(len(prices))]dp[0][0] = -prices[0] #持有股票dp[0][1] = 0for 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]-fee)return dp[-1][1]
相关文章:
Day50代码随想录动态规划part12:309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费
Day50 动态规划part12 股票问题 309.最佳买卖股票时机含冷冻期 leetcode题目链接:309. 买卖股票的最佳时机含冷冻期 - 力扣(LeetCode) 题意:给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。设计一个算…...
【软考】scrum的步骤
目录 1. 明确产品愿景和需求2. 制定计划和任务列表3. 进行迭代开发(Sprint)4. Sprint评审会议5. Sprint回顾会议6. 重复迭代 1. 明确产品愿景和需求 1.这个过程通常由项目所有者和利益相关者参与,目的是确保整个团队对项目的目标和方向有清晰…...

【C语言】编译与链接
✨✨欢迎大家来到Celia的博客✨✨ 🎉🎉创作不易,请点赞关注,多多支持哦🎉🎉 所属专栏:C语言 个人主页:Celias blog~ 目录 引言 一、翻译环境 1.1 编译 1.1.1 预处理 1.1.2 编译 …...
Consul 注册的服务地址变成了 127.0.1.1
问题 我们的服务一直用 Consul 作为注册中心,在 AWS 和 阿里云上使用的时候,没出现过问题。最近把一些服务迁到腾讯云的时候,遇到一个问题:注册的服务地址都是 127.0.1.1。 127.0.1.1 这个地址我们平时遇到的比较少,…...
数字水印 | 离散小波变换 DWT 的 Python 代码实现
🍍原文: 【图像处理】图像离散小波变换及 Python 代码实现 🍍写在前面: 本文在原文的基础上补全了代码。 1 环境准备 ① 安装 p y w t \mathsf{pywt} pywt 包: pip install PyWavelets说明: p y w t \…...
[框架] Unity 公共执行器
本篇我们通过使用单例模式来创建一个公共执行器,使得原本应该在Update()、FixedUpdate()中的指令都可以统一放在一个对象中执行,且可进行添加和移除操作。 1. 创建单例模式改造器:SingletonMono 我们先创建一个单例模式改造器,使…...

二进制转为HEX数组小工具
在使用RA8889时,JPG的解码只能从FLASH的DMA通道获取,那么如果要从远端、或者SD卡等处读取JPG图片出来显示怎么办? RA8889支持JPG图片硬解码,但数据流是从FLASH进行DMA读取的,然后再进行解码。因此这种情况下ÿ…...

数据结构-二叉树-红黑树
一、红黑树的概念 红黑树是一种二叉搜索树,但在每个节点上增加一个存储位表示节点的颜色,可以是Red或者BLACK,通过对任何一条从根到叶子的路径上各个节点着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,…...
C++11 新特性 decltype 说明符
一、typeof与typeid 1.1、typeof 在C11标准之前,GCC已经提供了一个类似功能的运算符 typeof对类型进行推导,但是这毕竟是编译器的实现,不是标准。 int a 0; typeof(a) b 5;1.2、typeid C标准提供了 typeid 运算符,获取的类型…...

java线程局部变量使用方式
线程局部变量是Java中用于存储线程本地信息的变量。这种变量仅在线程的生命周期内存在,并且每个线程都有自己的一份拷贝。换句话说,线程局部变量是线程私有的,其他线程无法访问。 使用场景主要包括: 1. 存储线程状态信息ÿ…...
【隧道篇 / WAN优化】(7.4) ❀ 01. 启动WAN优化 ❀ FortiGate 防火墙
【简介】几乎所有的人都知道,防火墙自带的硬盘是用来保存日志,以方便在出现问题时能找到原因。但是很少的人知道,防火墙自带的硬盘其实还有另一个功能,那就是用于WAN优化。 防火墙自带的硬盘 在FortiGate防火墙A、B、C、D系列&…...

2024数维杯数学建模B题生物质和煤共热解问题的研究原创论文分享
大家好,从昨天肝到现在,终于完成了2024数维杯数学建模挑战赛B题的完整论文啦。 实在精力有限,具体的讲解大家可以去讲解视频: 2024数维杯数学建模B题煤共热解每一问高质量完整代码讲解!_哔哩哔哩_bilibili 2024数维杯…...
中国电子学会(CEIT)2022年12月真题C语言软件编程等级考试三级(含详细解析答案)
中国电子学会(CEIT)考评中心历届真题(含解析答案) C语言软件编程等级考试一级 2022年12月 编程题五道 总分:100分一、鸡兔同笼(20分) 一个笼子里面关了鸡和兔子(鸡有2只脚,兔子有4只脚,没有例外)。已经知道了笼子里面脚的总数a,问笼子里面至少有多少只动物,至…...

今日早报 每日精选15条新闻简报 每天一分钟 知晓天下事 5月12日,星期日
每天一分钟,知晓天下事! 2024年5月12日 星期日 农历四月初五 1、 全国多地已推“一次挂号管三天”,部分医院专家门诊适用。 2、 在梅大高速塌方事故中拦车、救援,黄曼秋等5人拟确认为见义勇为。 3、 深圳新能源车指标申请条件调…...

微服务思想以及实现
文章目录 前言一、什么时候需要拆分微服务1. 创业型项目2. 大型项目 二、怎么拆1. 拆分目标2. 拆分方式 三、微服务之间远程调用1. 实现方式2. 手动发送Http请求(RestTemplate)3. 服务注册中心3.1 原理3.2 Nacos注册中心3.3 服务注册3.4 服务发现(Discov…...
C语法:格式符号%f和%lf引发的错误
今天编程时有如下代码: #include"stdio.h"int main(void) {double profit;double bonus;printf("请输入本月利润\n");scanf("%f",&profit);//错误:此行profit是double类型,格式符为%f,当输入8时࿰…...

Java基础入门day48
day48 JDBC调用关系 tomcat 简介 tomcat是Apache下的一个核心项目,免费开源,支持servlet和jsp。 tomcat技术先进,性能稳定,目前比较流行的web应用服务器 安装 官网: Apache Tomcat - Welcome! 下载 tomcat8.5 解压&a…...

C++笔记(体系结构与内核分析)
1.OOP面向对象编程 vs. GP泛型编程 OOP将data和method放在一起,目的是通过封装、继承、多态提高软件的可维护性和可扩展性GP将data和method分开,可以将任何容器与任何算法结合使用,只要容器满足塞饭所需的迭代器类型 2.算法与仿函数的区别 …...
c++ 唤醒指定线程
在C中,直接唤醒一个特定的线程并不像在Java的Thread类中有interrupt()方法或者某些操作系统特定的API(如POSIX的pthread_cond_signal或Windows的SetEvent)那样简单。C标准库没有提供一个直接的方法来"唤醒"一个正在等待的线程。然而…...

java报错:使用mybatis plus查询一个只返回一条数据的sql,却报错返回了1000多条
今天遇到一个问题 系统线上问题,经常出现这样的问题,刚重启系统时不报错了,可是运行一段时间又会出现。sql已经写了limit 1,mybatis的debug日志也返回total为1,可是却报错返回了1805条数据 乍一看,感觉太不…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...

P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...

AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...

Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
BLEU评分:机器翻译质量评估的黄金标准
BLEU评分:机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域,衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标,自2002年由IBM的Kishore Papineni等人提出以来,…...

给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...