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

【学会动态规划】买卖股票的最佳时机含手续费(16)

目录

动态规划怎么学?

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后:


动态规划怎么学?

学习一个算法没有捷径,更何况是学习动态规划,

跟我一起刷动态规划算法题,一起学会动态规划!

1. 题目解析

这道题也不难理解,主要有两个点需要注意,

首先是买了股票需要卖了才能再买(手里一次只能有一个股票)

买卖一次股票需要付一次手续费。

2. 算法原理

1. 状态表示

dp[ i ] 表示的是第 i 天结束之后,所能获得的最大利润,

实际上,这个也能细分成两种情况:

一种是第 i 天购买了股票,我们设为 f [ i ]

一种是第 i 天啥也不干,我们设为 g [ i ]

2. 状态转移方程

我们通过最近的一步来推导状态转移方程,总共需要分析两个:

如果第 i 天要进入买入股票的状态,那如果前一天已经买了,就什么都不用干,

如果第 i 天要进入买入股票的状态,如果前一天没买,那今天买就行,

所以 f [ i ] = max( f [ i - 1 ],g [ i - 1 ] - p [ i ] )

如果第 i 要进入卖出股票的状态,如果前一天没买,就啥都不用干,

如果第 i 要进入卖出股票的状态,如果前一天买了,那今天卖掉就行,

所以 g [ i ] = max( g [ i - 1 ],f [ i - 1 ] + p[ i ] - fee )

记得要减手续费 fee。

3. 初始化

f [ 0 ] = -p [ 0 ](就是买了当天的股票)g [ 0 ] = 0(啥都不干)

4. 填表顺序

从左往右,两个表同时填即可。

5. 返回值

g [ n - 1 ]

3. 代码编写

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

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

相关文章:

【学会动态规划】买卖股票的最佳时机含手续费(16)

目录 动态规划怎么学&#xff1f; 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后&#xff1a; 动态规划怎么学&#xff1f; 学习一个算法没有捷径&#xff0c;更何况是学习动态规划&#xff0c; 跟我…...

网络原因导致git下载报错处理办法

如下&#xff0c;git clone时报错&#xff1a; RPC failed; curl 18 transfer closed with outstanding read data remaining 5670 bytes of body are still expected fetch-pack: unexpected disconnect while reading sideband packet early EOF fetch-pack: invalid index…...

APP后端选择什么服务器

对于很多刚入行的朋友来说&#xff0c;不清楚应该选择什么样的服务器提供商&#xff0c;是选择传统的IDC, 租用服务器租用机柜&#xff0c;还是选择现在很火的云服务器呢&#xff1f;在本文中&#xff0c;通过对比传统的IDC和云服务&#xff0c;简单阐述一下服务器的选择。  …...

什么是反射机制,反射机制的应用场景

文章目录 反射机制介绍获取 Class 对象的四种方式代码实例静态编译和动态编译反射机制优缺点反射的应用场景 反射机制介绍 JAVA 反射机制是在运行状态中&#xff0c;对于任意一个类&#xff0c;都能够知道这个类的所有属性和方法&#xff1b;对于任意一个对象&#xff0c;都能…...

Visual Studio 2019 实用功能设置(背景颜色,代码字体及行号设置)

前言 Visual Studio 2019 安装包的下载教程、安装教程 教程 博主博客链接&#xff1a;https://blog.csdn.net/m0_74014525 关注博主&#xff0c;后期持续更新系列文章 系列文章 第一篇&#xff1a;Visual Studio 2019 详细安装教程&#xff08;图文版&#xff09; 第二篇&…...

简述Mysql索引

一、索引概述 1.1 索引概述 MySQL官方对索引的定义为&#xff1a;索引&#xff08;Index&#xff09;是帮助MySQL高效获取数据的数据结构。 索引的本质&#xff1a;索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”&#xff0c;满足特定查找算法。 这些数据结…...

windows .gitignore 加入文件名后 依然可以从git status中看到文件问题

最近在学git&#xff0c;对着b站的视频操作&#xff0c;结果很简单的添加.gitignore文件操作&#xff0c;up主的正常隐藏&#xff0c;我的却一直出问题。 百思不得其解&#xff0c;网上各种啥啥啥清缓存都没讲到点上。 最后发现是.gitignore文件有问题&#xff0c;windows默认…...

召唤神龙打造自己的ChatGPT

在之前的两篇文章中&#xff0c;我介绍了GPT 1和2的模型&#xff0c;并分别用Tensorflow和Pytorch来实现了模型的训练。具体可以见以下文章链接&#xff1a; 1. 基于Tensorflow来重现GPT v1模型_gzroy的博客-CSDN博客 2. 花费7元训练自己的GPT 2模型_gzroy的博客-CSDN博客 有…...

裝修公司同室內設計公司有咩分別?

很多裝修業主都會有裝修公司師傅會不會「出圖」的這個疑問。 出圖是指室內設計的各種圖&#xff0c;是設計師跟戶主和裝修師傅溝通裝修的工具&#xff0c;亦都係施工、驗收的證明。通常齊全的圖通常只有設計公司才可以完整提供例如平面圖、3D效果圖等等。 由於室內設計公司會…...

android oaid

Oaid获取接入流程 移动智能设备标识公共服务平台 AndroidID、IMEI、OAID获取 oaid_sdk_1.1.0的aar 随着Google对隐私的重视以及Android10的逐渐普及&#xff0c;获取设备的唯一标识越来越来难&#xff0c;在Android10以前&#xff0c;Android设备唯一标识包含IMEI、AndroidID、…...

利用XSS在线平台获取用户cookie

//XSS弹窗&#xff1a; <script>alert("xss")</script> XSS漏洞&#xff1a; //XSS弹窗&#xff1a; <script>alert("xss")</script> //XSS在线平台&#xff1a; <ScRipT sRc//7ix7kigpovxdbtd32fuspgffmtmufo3wwzgnzaltddewtb…...

rsync 命令以及脚本使用

rsync是什么&#xff1f; rsync 是一个远程同步工具 下载 你的集群每一台都需要下载&#xff01;&#xff08;也就是你需要同步的机器&#xff09; yum install -y xsync如果其他不下载就是报错的这样&#xff08;使用脚本的情况下&#xff0c;注意这里是提示 rsync没有找到…...

【数理知识】协方差,随机变量的的协方差,随机变量分别是单个数字和向量时的协方差

序号内容1【数理知识】自由度 degree of freedom 及自由度的计算方法2【数理知识】刚体 rigid body 及刚体的运动3【数理知识】刚体基本运动&#xff0c;平动&#xff0c;转动4【数理知识】向量数乘&#xff0c;内积&#xff0c;外积&#xff0c;matlab代码实现5【数理知识】协…...

WebDAV之π-Disk派盘+可达漫画

可达漫画这是一款专为阅读你的漫画收藏而设计的阅读器。 热爱漫画的你肯定收藏了不少各种类型的漫画,它们可能有各种各样的格式,zip,rar,cbz,cbr,epub, mobi 或 pdf,也可能只是单纯的文件夹。 可达漫画支持「流式阅读」,如果你的服务器使用 WebDAV 或 SMB 协议,那么…...

Spring中Bean的线程安全问题

Spring框架本身没有明确指出Bean的线程安全问题&#xff0c;所以Bean本身也不具备线程安全的特性&#xff0c;具体情况得看scope的情况。 1.原型的(prototype) 每次创建一个新的对象&#xff0c;每个线程使用的对象都是要新创建的&#xff0c;所以不会存在线程安全的问题。 2…...

Java spring boot 全解Camunda 7,从 0 到 1 构建工作流平台——第二节:Spring boot 简单集成

目录 1. 成果展示2. 环境准备3. 项目构建3.1 项目结构3.2 引入Camunda 依赖3.3 启动spring boot 程序3.4 启动 web app 程序 引言&#xff1a;当今技术发展迅猛&#xff0c;企业对于业务流程的高效管理和自动化需求也日益增长。在这个背景下&#xff0c;Spring Boot和Camunda7成…...

手持式静电测试仪的运用原理

手持式静电测试仪&#xff08;Handheld Electrostatic Test Meter&#xff09;是一种用于测量和检测静电电荷的便携式设备。它通常用于工业生产、实验室研究、防静电控制和监测等领域。 手持式静电测试仪可以帮助用户快速准确地测量物体表面静电电荷的状态&#xff0c;从而评估…...

【css问题】flex布局中,子标签宽度超出父标签宽度,导致布局出现问题

场景&#xff1a;文章标题过长时&#xff0c;只显示一行&#xff0c;且多余的部分用省略号显示。 最终效果图&#xff1a; 实现时&#xff0c;flex布局&#xff0c;出现问题&#xff1a; 发现text-overflow: ellipsis不生效&#xff0c;省略符根本没有出现。 而且因为设置了 …...

【vue3】前端应用中使用WebSocket与服务器进行通信并管理连接状态。

1、写一个hook函数 export const useWebsocketToStore ({ onMessage }): any > {const url ws:地址 Math.random()const onConnected () > {}const onDisconnected () > {}const onError () > {}const onMessageDefault (ws: WebSocket, event: MessageEve…...

服务端高并发分布式结构演进之路

目录 一、常见概念 1.1基本概念 二、架构演进 2.1单机架构 2.2应用数据分离架构 2.3应用服务集群架构 2.4读写分离 / 主从分离架构 2.5引入缓存 —— 冷热分离架构 2.6垂直分库 2.7业务拆分 —— 微服务 一、常见概念 1.1基本概念 应用&#xff08;Application&am…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...