动态规划 —— dp 问题-买卖股票的最佳时机含手续费

1. 买卖股票的最佳时机含手续费

题目链接:

714. 买卖股票的最佳时机含手续费 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/

 


2.  算法原理

状态表示:以某一个位置为结尾或者以某一个位置为起点

 

dp[i]表示:第i天结束之后,此时的最大利润 :两种情况:

 

                                1. f[i]表示:第i天结束之后,处于买入状态,此时的最大利润

  

                                2. g[i]表示:第i天结束之后,处于卖出状态,此时的最大利润

  

2. 状态转移方程

  

在第i-1天处于买入状态,看买入状态能不能到自己,看卖出状态能不能到买入状态,另一个状态也是如此,一共4种状态

   

买入状态到卖出状态到
买入状态什么都不干-prices[i](买股票)
卖出状态+prices[i](卖股票)-fee(手续费)什么都不干

1. f[i] = max(f[i-1],g[i-1]--prices[i])

  

2. g[i] = max(g[i-1],f[i-1]+prices[i]-fee)

  

3. 初始化 :把dp表填满不越界,让后面的填表可以顺利进行

  

f[0] = --prices[0]               g[0] = 0 

4. 填表顺序 

    

本题的填表顺序是:从左往右,两个表同时填

5. 返回值 :题目要求 + 状态表示    

    

因为是要最大利润,所以买入状态不用考虑  

本题的返回值是:g[n-1]

 


3. 代码 

动态规划的固定四步骤:1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表(填表方法:状态转移方程)

                                        4. 确定返回值

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
    //1.  创建dp表
        vector<int>f(n);
        auto g=f;

    //2. 在填表之前初始化
        f[0]=-prices[0];

    //3. 填表(填表方法:状态转移方程)
    for(int i=1;i<n;i++)
    {
        f[i]=max(f[i-1],g[i-1]-prices[i]);
        g[i]=max(g[i-1],f[i-1]+prices[i]-fee);
    }

    //4. 确定返回值
    return g[n-1];

    }
};


未完待续~ 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/912745.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

利用pythonstudio写的PDF、图片批量水印生成器,可同时为不同读者生成多组水印

现在很多场合需要将PDF或图片加水印&#xff0c;本程序利用pythonstudio编写。 第一步 界面 其中&#xff1a; LstMask:列表框 PopupMenu:PmnMark LstFiles:列表框 PopupMenu:PmnFiles OdFiles:文件选择器 Filter:PDF文件(.PDF)|.PDF|图像文件(.JPG)|.JPG|图像文件(.png…

基于python深度学习技术矩阵分解的推荐系统,通过学习隐含特征,实现推荐

实现了一个基于矩阵分解的推荐系统&#xff0c;用于预测用户对电影的评分。具体来说&#xff0c;该程序通过TensorFlow构建和训练一个模型&#xff0c;来学习用户和电影之间的隐含特征&#xff0c;并根据这些特征预测评分。以下是代码的主要功能和步骤的详细描述&#xff1a; …

[vulnhub] DarkHole: 1

https://www.vulnhub.com/entry/darkhole-1,724/ 端口扫描主机发现 探测存活主机&#xff0c;184是靶机 nmap -sP 192.168.75.0/24 Starting Nmap 7.94SVN ( https://nmap.org ) at 2024-11-08 09:59 CST Nmap scan report for 192.168.75.1 Host is up (0.00027s latency). MA…

4.1 WINDOWS XP,ReactOS对象与对象目录----1

系列文章目录 文章目录 系列文章目录4.1 对象与对象目录OBJECT_HEADERObpLookupEntryDirectory()NtCreateTimer() 4.1 对象与对象目录 “对象(Object)”这个词现在大家都已耳熟能详了&#xff0c;但是对象到底是什么呢?广义地说&#xff0c;对象就是“目标”&#xff0c;行为…

STM32H503开发(2)----STM32CubeProgrammer烧录

STM32H503开发----2.STM32CubeProgrammer烧录 概述硬件准备视频教学样品申请源码下载参考程序自举模式BOOT0设置UART烧录USB烧录 概述 STM32CubeProgrammer (STM32CubeProg) 是一款用于编程STM32产品的全功能多操作系统软件工具。 它提供了一个易用高效的环境&#xff0c;通过…

“双十一”电商狂欢进行时,在AI的加持下看网易云信IM、RTC如何助力商家!

作为一年一度的消费盛会&#xff0c;2024年“双十一”购物狂欢节早已拉开帷幕。蹲守直播间、在主播热情介绍中点开链接并加购&#xff0c;也已成为大多数人打开“双11”的重要方式。然而&#xff0c;在这火热的购物氛围背后&#xff0c;主播频频“翻车”、优质主播稀缺、客服响…

debian系统安装qt的时候 显示xcb相关文件缺失

如果是安装之后的问题 我们可以选择使用ldd的命令查看当前依赖的so那些文件确实 ldd /home/yinsir/Qt/5.15.2/gcc_64/plugins/platforms/libqxcb.so 本人在进行打包的时候 出现则会个报错 ERROR: ldd outputLine: “libxcb-util.so.1 > not found” ERROR: for binary: “/…

A023-基于SpringBoot的冷链物流系统的设计与实现

&#x1f64a;作者简介&#xff1a;在校研究生&#xff0c;拥有计算机专业的研究生开发团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 赠送计算机毕业设计600…

【数据分析】如何构建指标体系?

有哪些指标体系搭建模型&#xff1f;五个步骤教你从0开始搭建指标体系 一、企业指标体系搭建存在什么问题 许多企业在搭建数据指标体系时遇到了诸多难题&#xff0c;如问题定位不准确、数据采集不完整、目标不一致、报表无序、指标覆盖不全面以及报表价值未充分利用等。 1、…

C++20 概念与约束(1)—— SFINAE

1、从模板说起 众所周知&#xff0c;C在使用模板时&#xff0c;如果有多个模板匹配&#xff0c;则编译器会选择最匹配的一个模板进行实例化&#xff0c;这也正是模板特化和偏特化的依据。 根据上面这张图中的现象&#xff0c;列举下面几个示例&#xff1a; 1、不存在模板的情况…

基于Spring Boot的在线装修管理系统的设计与实现,LW+源码+讲解

摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对信息管理混乱&#xff0c;出错率高&#xff0c;信息安全性差&#…

原生鸿蒙应用市场:赋能开发者全生命周期服务体验

文章目录 背景自动化检测前移&#xff1a;早发现&#xff0c;早解决技术细节&#xff1a;静态代码分析与兼容性测试应用场景 按需加载&#xff1a;优化性能&#xff0c;提升用户体验技术细节&#xff1a;模块化与懒加载实现应用场景 应用加密&#xff1a;保护应用代码安全&…

RDD 算子全面解析:从基础到进阶与面试要点

Spark 的介绍与搭建&#xff1a;从理论到实践_spark环境搭建-CSDN博客 Spark 的Standalone集群环境安装与测试-CSDN博客 PySpark 本地开发环境搭建与实践-CSDN博客 Spark 程序开发与提交&#xff1a;本地与集群模式全解析-CSDN博客 Spark on YARN&#xff1a;Spark集群模式…

配置多公钥在多平台使用Git

步骤很详细&#xff0c;直接上教程 当我们想在不同远程仓库平台配置不同公钥时会发现不进行额外配置是不行的&#xff0c;只会使用默认的公钥&#xff0c;本篇文章便是为了解决这个问题 进入C:\Users\[你的用户名]\.ssh文件夹 如果没有这个文件夹可以新建一下 在上述文件夹新建…

如何在 Android 上增加 SELinux 权限

SELinux&#xff08;Security-Enhanced Linux&#xff09;是一种强制访问控制&#xff08;MAC&#xff09;机制&#xff0c;它为 Android 系统提供了额外的安全层。通过 SELinux&#xff0c;系统管理员可以定义细粒度的安全策略&#xff0c;限制进程对文件、网络和其他资源的访…

新能源汽车与公共充电桩布局

近年来,全球范围内对新能源汽车产业的推动力度不断增强,中国新能源汽车市场也呈现蓬勃发展的势头,在政策与市场的共同推动下,新能源汽车销量持续增长。然而,据中国充电联盟数据显示,充电基础设施建设滞后于新能源汽车数量增长的现状导致充电桩供需不平衡,公共充电桩服务空白区域…

中科大:LLM知识遗忘评估与优化

&#x1f4d6;标题&#xff1a;A Closer Look at Machine Unlearning for Large Language Models &#x1f310;来源&#xff1a;arXiv, 2410.08109 &#x1f31f;摘要 &#x1f538;大型语言模型&#xff08;LLM&#xff09;可能会记住敏感或受版权保护的内容&#xff0c;从…

django+postgresql

PostgreSQL概述 PostgreSQL 是一个功能强大的开源关系数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;以其高度的稳定性、扩展性和社区支持而闻名。PostgreSQL 支持 SQL 标准并具有很多先进特性&#xff0c;如 ACID 合规、复杂查询、外键支持、事务处理、表分区、JS…

Flink CEP 入门

1&#xff0e;复杂事件处理 大数据应用领域存在业务逻辑非常复杂的应用系统&#xff0c;比如&#xff0c;一个应用要检测特定顺序先后发生的一组事件&#xff0c;对事件组进行分析或报警提示&#xff0c;若使用SQL 或者DataStream API 处理这类应用&#xff0c;过程相对来说比较…

CSS教程(三)- CSS 三大特性

1. 层叠性 介绍 多组CSS样式共同作用于一个元素&#xff0c;就会出现 覆盖&#xff08;层叠&#xff09; 另一个冲突的样式。 层叠原则 样式冲突&#xff1a;遵循就近原则&#xff08;哪个样式离结构近&#xff0c;就执行哪个样式&#xff09; 样式不冲突&#xff0c;就不会重…