【学会动态规划】买卖股票的最佳时机含手续费(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…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
