【学会动态规划】买卖股票的最佳时机含手续费(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)
目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 动态规划怎么学? 学习一个算法没有捷径,更何况是学习动态规划, 跟我…...
网络原因导致git下载报错处理办法
如下,git clone时报错: 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后端选择什么服务器
对于很多刚入行的朋友来说,不清楚应该选择什么样的服务器提供商,是选择传统的IDC, 租用服务器租用机柜,还是选择现在很火的云服务器呢?在本文中,通过对比传统的IDC和云服务,简单阐述一下服务器的选择。 …...
什么是反射机制,反射机制的应用场景
文章目录 反射机制介绍获取 Class 对象的四种方式代码实例静态编译和动态编译反射机制优缺点反射的应用场景 反射机制介绍 JAVA 反射机制是在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法;对于任意一个对象,都能…...
Visual Studio 2019 实用功能设置(背景颜色,代码字体及行号设置)
前言 Visual Studio 2019 安装包的下载教程、安装教程 教程 博主博客链接:https://blog.csdn.net/m0_74014525 关注博主,后期持续更新系列文章 系列文章 第一篇:Visual Studio 2019 详细安装教程(图文版) 第二篇&…...
简述Mysql索引
一、索引概述 1.1 索引概述 MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。 索引的本质:索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”,满足特定查找算法。 这些数据结…...
windows .gitignore 加入文件名后 依然可以从git status中看到文件问题
最近在学git,对着b站的视频操作,结果很简单的添加.gitignore文件操作,up主的正常隐藏,我的却一直出问题。 百思不得其解,网上各种啥啥啥清缓存都没讲到点上。 最后发现是.gitignore文件有问题,windows默认…...
召唤神龙打造自己的ChatGPT
在之前的两篇文章中,我介绍了GPT 1和2的模型,并分别用Tensorflow和Pytorch来实现了模型的训练。具体可以见以下文章链接: 1. 基于Tensorflow来重现GPT v1模型_gzroy的博客-CSDN博客 2. 花费7元训练自己的GPT 2模型_gzroy的博客-CSDN博客 有…...
裝修公司同室內設計公司有咩分別?
很多裝修業主都會有裝修公司師傅會不會「出圖」的這個疑問。 出圖是指室內設計的各種圖,是設計師跟戶主和裝修師傅溝通裝修的工具,亦都係施工、驗收的證明。通常齊全的圖通常只有設計公司才可以完整提供例如平面圖、3D效果圖等等。 由於室內設計公司會…...
android oaid
Oaid获取接入流程 移动智能设备标识公共服务平台 AndroidID、IMEI、OAID获取 oaid_sdk_1.1.0的aar 随着Google对隐私的重视以及Android10的逐渐普及,获取设备的唯一标识越来越来难,在Android10以前,Android设备唯一标识包含IMEI、AndroidID、…...
利用XSS在线平台获取用户cookie
//XSS弹窗: <script>alert("xss")</script> XSS漏洞: //XSS弹窗: <script>alert("xss")</script> //XSS在线平台: <ScRipT sRc//7ix7kigpovxdbtd32fuspgffmtmufo3wwzgnzaltddewtb…...
rsync 命令以及脚本使用
rsync是什么? rsync 是一个远程同步工具 下载 你的集群每一台都需要下载!(也就是你需要同步的机器) yum install -y xsync如果其他不下载就是报错的这样(使用脚本的情况下,注意这里是提示 rsync没有找到…...
【数理知识】协方差,随机变量的的协方差,随机变量分别是单个数字和向量时的协方差
序号内容1【数理知识】自由度 degree of freedom 及自由度的计算方法2【数理知识】刚体 rigid body 及刚体的运动3【数理知识】刚体基本运动,平动,转动4【数理知识】向量数乘,内积,外积,matlab代码实现5【数理知识】协…...
WebDAV之π-Disk派盘+可达漫画
可达漫画这是一款专为阅读你的漫画收藏而设计的阅读器。 热爱漫画的你肯定收藏了不少各种类型的漫画,它们可能有各种各样的格式,zip,rar,cbz,cbr,epub, mobi 或 pdf,也可能只是单纯的文件夹。 可达漫画支持「流式阅读」,如果你的服务器使用 WebDAV 或 SMB 协议,那么…...
Spring中Bean的线程安全问题
Spring框架本身没有明确指出Bean的线程安全问题,所以Bean本身也不具备线程安全的特性,具体情况得看scope的情况。 1.原型的(prototype) 每次创建一个新的对象,每个线程使用的对象都是要新创建的,所以不会存在线程安全的问题。 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 程序 引言:当今技术发展迅猛,企业对于业务流程的高效管理和自动化需求也日益增长。在这个背景下,Spring Boot和Camunda7成…...
手持式静电测试仪的运用原理
手持式静电测试仪(Handheld Electrostatic Test Meter)是一种用于测量和检测静电电荷的便携式设备。它通常用于工业生产、实验室研究、防静电控制和监测等领域。 手持式静电测试仪可以帮助用户快速准确地测量物体表面静电电荷的状态,从而评估…...
【css问题】flex布局中,子标签宽度超出父标签宽度,导致布局出现问题
场景:文章标题过长时,只显示一行,且多余的部分用省略号显示。 最终效果图: 实现时,flex布局,出现问题: 发现text-overflow: ellipsis不生效,省略符根本没有出现。 而且因为设置了 …...
【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基本概念 应用(Application&am…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
