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

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...