当前位置: 首页 > 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…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...