动态规划-简单多状态dp问题——714.买卖股票的最佳时机含手续费

1.题目解析

题目来源:714.买卖股票的最佳时机含手续费——力扣

测试用例

2.算法原理

1.状态表示

本题有两种状态,一种是卖出状态一种是买入状态

我们创建两个dp表来分别存储这两种状态,f[]表示买入,g[]表示卖出

f[i]表示第i个位置处于买入状态时的最大利润,g[i]表示第i个位置处于卖出状态的最大利润

2.状态转移方程 

买入与卖出两种状态是可以相互转换的,也就是题目中说的可以随意买卖,但是有手续费

此时如果要求第i个位置的最大利润需要对两种状态分类讨论

a.第i个位置处于买入状态:此时第i-1个位置可以是买入也可以是卖出,如果是买入则直接取第i-1个位置的利润即可,如果是卖出则需要减去第i个位置的股票价格,由于手续费在买卖时只需要付一次,因此我们可以在卖出时再付手续费

b.第i个位置处于卖出状态:此时第i-1个位置可以是买入也可以是卖出,如果是买入说明此时第i个位置就是交易位置,此时加上该位置的股票售价并付手续费,如果是卖出则直接取第i-1个位置的利润即可

3.初始化

每个位置都需要前一个位置计算,因此需要初始化两个dp表的第一个位置,f的第一个位置代表买入,则等于-prices[0],g的第一个位置代表卖出,此时没有买卖股票则为0

4.填表顺序

从左到右,两个表一起填

5.返回值 

由于最后手中持有股票一定无法获得最大利润,因此只需要返回最后一个位置卖出状态的利润即可

3.实战代码

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();vector<int> f(n);vector<int> g(n);f[0] = -prices[0];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);}return g[n-1];}
};

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

一个Idea:爆改 T480

爆改 T480 准备大改 T480&#xff0c;家里有一台闲置很久的 T480&#xff0c;不舍得扔&#xff0c;打算升级一下。看了几位up主的视频后&#xff0c;决定动手改造。 计划如下 网卡&#xff1a;加装4G网卡硬盘&#xff1a;更换为 1T 的 NVMe 2280 固态硬盘内存&#xff1a;升…

WordPress添加meta标签做seo优化

一、使用function.php文件添加钩子函数添加 方法1、使用is_page()判断不同页面的page_id进行辨别添加不同页面keyword和description &#xff08;1&#xff09;通过页面前台源码查看对应页面的id &#xff08;2&#xff09;或者通过wordpress后台&#xff0c;点击页面列表&…

基于BeautyEye开发Java程序用户界面

文章目录 I idea引入jar包添加本地jar包maven方式引入本地包方式1:将第三方JAR包安装到本地仓库maven方式引入本地包方式2:引用本地路径将本地jar包打进war包Maven内置变量说明II BeautyEye Swing外观实现方案案例III 知识扩展Swing常用的顶级容器BeautyEye SwingI idea引入j…

南京邮电大学电工电子A实验十二(集成触发器及其应用和计数与分频电路)

文章目录 一、实验报告预览二、Word版本报告下载 一、实验报告预览 二、Word版本报告下载 点我

6本“灌水神刊”SCI,沾边可录,可选非OA,1个月Accept!

01 录用快刊 1、Drones • 影响因子&#xff1a;4.4 • 期刊分区&#xff1a;JCR1区&#xff0c;中科院2区 • 检索数据库&#xff1a;SCI • 征稿领域&#xff1a;该杂志主要关注无人机的设计和应用&#xff0c;包括无人机&#xff08;UAV&#xff09;、无人机系统&#x…

100. UE5 GAS RPG 显示范围魔法的攻击范围

在这一篇里&#xff0c;我们将制作一个范围魔法&#xff0c;释放魔法时&#xff0c;我们将在鼠标拾取位置绘制一个魔法光圈&#xff0c;用于显示技能释放时攻击的范围&#xff0c;然后再次点击可以释放技能。 创建贴花类 魔法范围标识的光圈&#xff0c;我们采用贴花实现&…

测试200个用户在10秒之内同时访问百度的网页

右键添加->线程->线程组 得到下面的截图 线程数&#xff1a;就是模仿用户并发的数量&#xff0c;Ramp-up:运行线程的总时间&#xff0c;单位是秒&#xff0c;循环次数&#xff1a;就是每个线程循环多少次。 现在的线程数是200&#xff0c;就是相当于有200个用户&#xff…

Internet Download Manager下载器2025绿色版带你飞一般的下载体验

Internet Download Manager下载器&#xff1a;带你飞一般的下载体验 &#x1f31f; **极速下载&#xff0c;秒变大神&#xff01;** 兄弟姐妹们&#xff0c;还在为龟速的下载速度抓狂吗&#xff1f;&#x1f620; 今天要给大家安利一款神奇的下载神器——Internet Download Ma…

Linux升级openssl版本

Linux升级openssl版本 服务器编译依赖库检查 $ yum -y install gcc gcc-c make libtool zlib zlib-devel版本检测 $ openssl version OpenSSL 1.0.1e-fips 11 Feb 2013 $ ssh -V OpenSSH_6.6.1p1, OpenSSL 1.0.1e-fips 11 Feb 2013下载openssl 地址&#xff1a;https://www.o…

Linux的hadoop集群部署

1.hadoop是一个分布式系统基础架构,主要解决海量数据额度存储与海量数据的分析计算问题 hdfs提供存储能力,yarn提供资源管理能力,MapReduce提供计算能力 2.安装 一:调整虚拟机内存,4G即可 二:下载安装包 网址:https://mirrors.aliyun.com/apache/hadoop/common/hadoop-3.4.0/…

Java知识巩固(五)

目录 基本数据类型 基本类型和包装类型的区别&#xff1f; 自动装箱与拆箱了解吗?原理是什么&#xff1f; 为什么浮点数运算的时候回邮精度丢失的风险&#xff1f; 如何解决浮点数运算的精度丢失问题&#xff1f; 超过 long 整型的数据应该如何表示&#xff1f; 基本数据…

javaWeb项目-Springboot+vue-车辆管理系统功能介绍

本项目源码&#xff08;点击下方链接下载&#xff09;&#xff1a;java-springbootvue车辆管理系统设计与实现源码(项目源码-说明文档)_若依检车管理系统资源-CSDN文库 项目关键技术 开发工具&#xff1a;IDEA 、Eclipse 编程语言: Java 数据库: MySQL5.7 框架&#xff1a;ssm…

Sentinel最全笔记,详细使用步骤教程清单

一、Sentinel的基本功能 1、流量控制 流量控制在网络传输中是一个常用的概念&#xff0c;它用于调整网络包的发送数据。然而&#xff0c;从系统稳定性角度考虑&#xff0c;在处理请求的速度上&#xff0c;也有非常多的讲究。任意时间到来的请求往往是随机不可控的&#xff0c;…

SpringCloud无介绍快使用,sentinel服务熔断功能与持久化(二十四)

TOC 问题背景 从零开始学springcloud微服务项目 注意事项&#xff1a; 约定 > 配置 > 编码IDEA版本2021.1这个项目&#xff0c;我分了很多篇章&#xff0c;每篇文章一个操作步骤&#xff0c;目的是显得更简单明了controller调service&#xff0c;service调dao默认安装ngi…

python项目实战——下载美女图片

python项目实战——下载美女图片 文章目录 python项目实战——下载美女图片完整代码思路整理实现过程使用xpath语法找图片的链接检查链接是否正确下载图片创建文件夹获取一组图片的链接获取页数 获取目录页的链接 完善代码注意事项 完整代码 import requests import re import…

2023年“网络建设与运维”广西省赛试题复盘

2023年“网络搭建与应用”省赛试题复盘 第一部分&#xff1a;网络搭建及安全部署项目 &#xff08;500分&#xff09; 一、竞赛内容分布 “网络搭建与应用”竞赛共分二个部分&#xff0c;其中&#xff1a; 第一部分&#xff1a;网络搭建及安全部署项目 第二部分&#xff1a;服…

什么是Qseven?模块电脑(核心板)规范标准简介二

1.概念 Qseven是一种通用的、小尺寸计算机模块标准&#xff0c;适用于需要低功耗、低成本和高性能的应用。 Qseven模块电脑&#xff08;核心板&#xff09;采用230Pin金手指连接器 2.Qseven的起源 Qseven最初是由Congatec、SECO、MSC三家欧洲公司于2008年发起&#xff0c;旨在…

简单聊聊 限流算法

计数器 计数器算法&#xff0c;是在一个时间间隔内&#xff0c;比如一分钟内&#xff0c;对请求进行计数&#xff0c;然后将计数值和设置的最大值进行比较&#xff0c;如果超过了最大值&#xff0c;进行限流处理&#xff0c;拒绝请求。 他的优点是&#xff1a;算法简单&#…

OpenAI持续open,meta prompt开源

目录 前言 提示&#xff08;Prompts&#xff09; Playground中的元提示借鉴了OpenAI提示工程最佳实践和用户的实际经验。 模式&#xff08;Schemas&#xff09; 自描述模式 -元模式。 虽然OpenAI目前使用元提示和模式&#xff0c;但将来可能会集成更先进的技术&#xff0c…

仓库管理系统有哪些功能?

上一篇&#xff0c;我们向大家介绍了一下仓库管理是什么&#xff0c;仓库管理操作流程有哪些&#xff0c;仓库管理系统又有哪些基本功能&#xff0c;那么接下来这篇文章&#xff0c;我们会详细介绍一下仓库管理系统各个功能是如何运作&#xff0c;是怎样解决企业中碰到的难题的…