代码随想录算法训练营day46|动态规划09

买卖股票的最佳时机四

之前是最多只能完成两笔交易,现在是至多可以买卖k次,那么状态数需要定为2*k+1种,此时,就要分析多种情况的递推式
找到奇偶数交替的规则即可

class Solution {
public:int maxProfit(int k, vector<int>& prices) {if(prices.size()==0) return 0;vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0));for(int j=1;j<2*k;j+=2){dp[0][j]=-prices[0];}for(int i=1;i<prices.size();++i){for(int j=0;j<2*k-1;j+=2){dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i]);dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);}}return dp[prices.size()-1][2*k];}
};

最佳买卖股票时机含冷冻期

如何去分离状态使得包含所有情况,又能更简单的得到递推式
在这里插入图片描述

class Solution {
public:int maxProfit(int k, vector<int>& prices) {if(prices.size()==0) return 0;vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0));for(int j=1;j<2*k;j+=2){dp[0][j]=-prices[0];}for(int i=1;i<prices.size();++i){for(int j=0;j<2*k-1;j+=2){dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i]);dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);}}return dp[prices.size()-1][2*k];}
};

最佳买卖股票时机含手续费

动态规划理解起来比贪心简单很多
只需加一个扣手续费即可

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n=prices.size();vector<vector<int>> dp(n,vector<int>(2,0));dp[0][0]=-prices[0];for(int i=1;i<n;++i){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);}return max(dp[n-1][0],dp[n-1][1]);}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/479062.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

前端-Git

一.基本概念 Git版本控制系统时一个分布式系统&#xff0c;是用来保存工程源代码历史状态的命令行工具 简单来说Git的作用就是版本管理工具。 Git的应用场景&#xff1a;多人开发管理代码&#xff1b;异地开发&#xff0c;版本管理&#xff0c;版本回滚。 Git 的三个区域&a…

【软件介绍】变声工具RVC本地部署使用方法

RVC&#xff08;Real-Time Voice Conversion&#xff09;软件是一种能够实现实时声音转换的技术工具&#xff0c;它允许用户改变自己或他人的语音特征&#xff0c;比如音调、音色等&#xff0c;以达到变声的效果。这种技术在娱乐、游戏、内容创作等领域有着广泛的应用。下面是一…

IntelliJ IDEA 中,自动导包功能

在 IntelliJ IDEA 中&#xff0c;自动导包功能可以极大地提高开发效率&#xff0c;减少手动导入包所带来的繁琐和错误。以下是如何在 IntelliJ IDEA 中设置和使用自动导包功能的详细步骤&#xff1a; 一、设置自动导包 打开 IntelliJ IDEA&#xff1a; 启动 IntelliJ IDEA 并打…

【CANOE】【Capl】【RS232】控制串口设备

系列文章目录 内置函数&#xff0c;来控制传统的串口设备&#xff0c;比如继电器等 文章目录 系列文章目录前言一、控制串口二、自定义相关的参数RS232Configure**函数语法****函数功能****参数说明****返回值****示例代码** 三、回调函数的使用RS232OnSend**函数语法****函数…

AX58100+STM32使用FSMC接口,运行EtherCAT Slave协议栈

目录 简介环境硬件接线MCU一侧的初始化时钟FSMC外部中断timer 协议栈生成EtherCAT SlaveSlave infomationgenerichardwareEtherCAT State MachineSynchronisationApplicaitonProcessDataMailbox OD TOOL 协议栈移植协议栈集成和错误初步解决启动协议栈 应用开发集成到TWINCAT集…

IC数字后端实现之大厂IC笔试真题(经典时序计算和时序分析题)

今天小编给大家分享下每年IC秋招春招必考题目——静态时序分析时序分析题。 数字IC后端笔试面试题库 | 经典时序Timing计算题 时序分析题1&#xff1a; 给定如下图所示的timing report&#xff0c;请回答一下几个问题。 1&#xff09;这是一条setup还是hold的timing report?…

嵌入式系统与OpenCV

目录 一、OpenCV 简介 二、嵌入式 OpenCV 的安装方法 1. Ubuntu 系统下的安装 2. 嵌入式 ARM 系统中的安装 3. Windows10 和树莓派系统下的安装 三、嵌入式 OpenCV 的性能优化 1. 介绍嵌入式平台上对 OpenCV 进行优化的必要性。 2. 利用嵌入式开发工具&#xff0c;如优…

英伟达发布 Edify 3D 生成模型,可以在两分钟内生成详细的、可用于生产的 3D 资源、生成有组织的 UV 贴图、4K 纹理和 PBR 材质。

英伟达发布 Edify 3D 生成模型&#xff0c;可以利用 Agents 自动判断提示词场景中需要的模型&#xff0c;生成后将他们组合为一个场景。 Edify 3D 可以在两分钟内生成详细的、可用于生产的 3D 资源、生成有组织的 UV 贴图、4K 纹理和 PBR 材质。 相关链接 论文&#xff1a;htt…

抖音短视频矩阵源代码部署搭建流程

抖音短视频矩阵源代码部署搭建流程 1. 硬件准备 需确保具备一台性能足够的服务器或云主机。这些硬件设施应当拥有充足的计算和存储能力&#xff0c;以便支持抖音短视频矩阵系统的稳定运行。 2. 操作系统安装 在选定的服务器或云主机上安装适合的操作系统是关键步骤之一。推…

【Android+多线程】异步 多线程 知识总结:基础概念 / 多种方式 / 实现方法 / 源码分析

1 基本概念 1.1 线程 定义&#xff1a;一个基本的CPU执行单元 & 程序执行流的最小单元 比进程更小的可独立运行的基本单位&#xff0c;可理解为&#xff1a;轻量级进程组成&#xff1a;线程ID 程序计数器 寄存器集合 堆栈注&#xff1a;线程自己不拥有系统资源&#…

NLP论文速读(剑桥大学出品)|分解和利用专家模型中的偏好进行改进视觉模型的可信度

论文速读|Decompose and Leverage Preferences from Expert Models for Improving Trustworthiness of MLLMs 论文信息&#xff1a; 简介&#xff1a; 本文探讨的背景是多模态大型语言模型&#xff08;MLLMs&#xff09;&#xff0c;这类模型通过结合视觉特征和文本空间来增强语…

CentOS8.5.2111(7)完整的Apache综合实验

一、实验目标 1.掌握Linux系统中Apache服务器的安装与配置&#xff1b; 2.掌握个人主页、虚拟目录、基于用户和主机的访问控制及虚拟主机的实现方法。 二、实验要求 练习使用linux系统下WEB服务器的配置方法。 三、实验背景 重庆工程学院为筹备“重庆工程大学”特申请了c…

零基础3分钟快速掌握 ——Linux【终端操作】及【常用指令】Ubuntu

1.为啥使用Linux做嵌入式开发 能广泛支持硬件 内核比较高效稳定 原码开放、软件丰富 能够完善网络通信与文件管理机制 优秀的开发工具 2.什么是Ubuntu 是一个以桌面应用为主的Linux的操作系统&#xff0c; 内核是Linux操作系统&#xff0c; 具有Ubuntu特色的可视…

JVM类加载和垃圾回收算法详解

文章目录 JVM一、JVM运行流程1. JVM执行流程 二、JVM运行时数据区1. 程序计数器&#xff08;线程私有&#xff09;2. 虚拟机栈 &#xff08;线程私有&#xff09;3. 本地方法栈&#xff08;线程私有&#xff09;4. 堆&#xff08;线程共享&#xff09;5. 元空间&#xff08;线程…

iOS 17.4 Not Installed

0x00 系统警告 没有安装 17.4 的模拟器&#xff0c;任何操作都无法进行&#xff01; 点击 OK 去下载&#xff0c;完成之后&#xff0c;依旧是原样&#xff01; 0x01 解决办法 1、先去官网下载对应的模拟器&#xff1a; https://developer.apple.com/download/all/?q17.4 …

day04 企业级Linux安装及远程连接知识实践

1. 使用传统的网卡命名方式 在启动虚拟机时&#xff0c;按tab键进入编辑模式 添加命令&#xff1a; net.ifnames0 biosdevname0 这样linux系统会使用传统的网卡命名&#xff0c;例如eth0、eth1…… 2. 快照 做系统关键操作时&#xff0c;一定要使用快照(先将系统关机) 3.…

人体特定吸收率 (SAR) 分布建模

ANSYS HFSS 提供了一种建模 SAR 分布的方法&#xff01; 2020 年对我们所有人来说都是充满挑战的一年&#xff0c;由于 COVID 19 限制和居家隔离&#xff0c;许多工程师不得不推迟开发时间表。ANSYS HFSS 为所有工程师提供了一种在家安全工作的好方法。隔离期间&#xff0c;您…

.NET9 - Swagger平替Scalar详解(四)

书接上回&#xff0c;上一章介绍了Swagger代替品Scalar&#xff0c;在使用中遇到不少问题&#xff0c;今天单独分享一下之前Swagger中常用的功能如何在Scalar中使用。 下面我们将围绕文档版本说明、接口分类、接口描述、参数描述、枚举类型、文件上传、JWT认证等方面详细讲解。…

计算(a+b)/c的值

计算&#xff08;ab&#xff09;/c的值 C语言代码C语言代码Java语言代码Python语言代码 &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; 给定3个整数a、b、c&#xff0c;计算表达式(ab)/c的值&#xff0c;/是整除运算。 输入 输入仅一行&…

PICO 获取设备号 SN码

Unity版本 2020.3.42f1c1PICO SDK版本PICO Unity Integration SDK-3.0.5-20241105Pico设备pico 4ultra 注意 此api暂时只测试企业版本 pico 4ultra 代码 using Unity.XR.PICO.TOBSupport;private void Awake() {bool result PXR_Enterprise.InitEnterpriseService();Debug.L…