当前位置: 首页 > news >正文

day-50 代码随想录算法训练营(19)动态规划 part 11

123.买卖股票的最佳时机|||

分析:只能买卖两次,就是说有五个状态:
  • 没有买过
  • 第一次买入
  • 第一次卖出
  • 第二次买入
  • 第二次卖出
思路:二维数组,记录五个状态
  • 1.dp存储:dp[i][1] 第一次买入   dp[i][2] 第一次卖出  dp[i][3] 第二次买入  dp[i][4] 第二次卖出
  • 2.dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
    • dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i])
    • dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i])
    • dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i])
  • 3.初始化:dp[0][1]=-prices[0]    dp[0][3]=-prices[0]
  • 4.遍历顺序:1~n
class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>> dp(n,vector<int>(5,0));dp[0][1]=-prices[0];dp[0][3]=-prices[0];for(int i=1;i<n;i++){dp[i][0]=dp[i-1][0];//第一天不持有dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]);dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i]);dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]);}return dp[n-1][4];}
};

188.买卖股票的最佳时机IV

分析:买卖几次成了变量
思路:
  • 1.dp存储:2k+1个状态的买卖金额
  • 2.动态转移方程(递推式):
    • j奇数:dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i])
    •  j偶数:dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i])
  • 3.初始化:j奇数:dp[i][j]=-prices[0]
  • 4.遍历顺序:1-n
class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n=prices.size();int m=k*2;vector<vector<int>>dp(n,vector<int>(m+1,0));for(int i=1;i<=m;i+=2) dp[0][i]=-prices[0]; //初始化for(int i=1;i<n;i++){dp[i][0]=dp[i-1][0];//第一天不持有for(int j=1;j<m+1;j++){if(j%2!=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i]);//第j天持有else dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i]);//第j天卖出}}return dp[n-1][m];}
};

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

分析:现在有四种状态:买入股票 冷冻期后没买入   卖出股票   冷冻期
思路:dp存储四种状态
  • 1.dp存储:四种状态
  • 2.动态转移方程(递推式):
    • dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]))
    • dp[i][1]=max(dp[i-1][1],dp[i-1][3])
    • dp[i][2]=dp[i-1][0]+prices[i]
    • dp[i][3]=dp[i-1][2]
  • 3.初始化:dp[0][0]=-prices[0]
  • 4.遍历顺序:1~n
class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(4,0));dp[0][0]=-prices[0];for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));//持有dp[i][1]=max(dp[i-1][1],dp[i-1][3]);//冷冻期后面不持有dp[i][2]=dp[i-1][0]+prices[i];//卖出dp[i][3]=dp[i-1][2];//冷冻期}return max(dp[n-1][3],max(dp[n-1][1],dp[n-1][2]));//最大值一定不持有}
};

相关文章:

day-50 代码随想录算法训练营(19)动态规划 part 11

123.买卖股票的最佳时机||| 分析&#xff1a;只能买卖两次&#xff0c;就是说有五个状态&#xff1a; 没有买过第一次买入第一次卖出第二次买入第二次卖出 思路&#xff1a;二维数组&#xff0c;记录五个状态 1.dp存储&#xff1a;dp[i][1] 第一次买入 dp[i][2] 第一次卖…...

自定义权限指令与防止连点指令

1.权限指令 // 注册一个全局自定义权限指令 v-permission Vue.directive(permission, {inserted: function(el, binding, vnode) {const {value} binding; // 指令传的值// user:edit:phone,sysData:sampleconst permissions [user:edit:address, sysData:entrust, sysData:…...

UE5、CesiumForUnreal实现瓦片坐标信息图层效果

文章目录 1.实现目标2.实现过程2.1 原理简介2.2 cesium-native改造2.3 CesiumForUnreal改造2.4 运行测试3.参考资料1.实现目标 参考CesiumJs的TileCoordinatesImageryProvider,在CesiumForUnreal中也实现瓦片坐标信息图层的效果,便于后面在调试地形和影像瓦片的加载调度等过…...

PostgreSQL执行计划

1. EXPLAIN命令 1)PostgreSQL中EXPLAIN命令的语法格式: postgres# \h explain Command: EXPLAIN Description: show the execution plan of a statement Syntax: EXPLAIN [ ( option [, ...] ) ] statement EXPLAIN [ ANALYZE ] [ VERBOSE ] statementwhere option can be…...

【2023 睿思芯科 笔试题】~ 题目及参考答案

文章目录 1. 题目 & 答案单选题编程题问题1&#xff1a;解析1&#xff1a;问题2&#xff1a;解析2&#xff1a; 声明 名称如标题所示&#xff0c;希望大家正确食用&#xff08;点赞转发评论&#xff09; 本次笔试题以两种形式考察的&#xff0c;分别是&#xff1a;选择题&a…...

Java手写AVL树

Java手写AVL树 1. AVL树实现思路原理 为了解释AVL树的实现思路原理&#xff0c;下面使用Mermanid代码表示该算法的思维导图&#xff1a; #mermaid-svg-ycH8kKpzVk2HWEby {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid…...

运维自动化:提高效率的秘诀

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…...

C++设计模式_05_Observer 观察者模式

接上篇&#xff0c;本篇将会介绍C设计模式中的Observer 观察者模式&#xff0c;和前2篇模板方法Template Method及Strategy 策略模式一样&#xff0c;仍属于“组件协作”模式。Observer 在某些领域也叫做 Event 。 文章目录 1. 动机&#xff08; Motivation&#xff09;2. 代码…...

github网站打不开,hosts文件配置

首先获取github官网的ip地址&#xff0c; 打开cmd&#xff0c;输入ping github.com 配置&#xff1a; #github 140.82.114.4 github.com 199.232.69.194 github.global.ssl.fastly.net 185.199.108.153 assets-cdn.github.com 185.199.110.153 assets-cdn.github.com 185.199…...

总结PCB设计的经验

一般PCB基本设计流程如下&#xff1a;前期准备->PCB结构设计->PCB布局->布线->布线优化和丝印->网络和DRC检查和结构检查->制版。: :   第一&#xff1a;前期准备。这包括准备元件库和原理图。“工欲善其事&#xff0c;必先利其器”&#xff0c;要做出一…...

HCIE-HCS规划设计搭建

1、相关术语 1、等价路由 等价路由&#xff08;Equal-cost routing&#xff09;是一种网络路由策略&#xff0c;用于在网络中选择多个具有相同路由度量&#xff08;路由距离或成本&#xff09;的最佳路径之一来转发数据流量。 当存在多个路径具有相同的路由度量时&#xff0c;…...

c语言输出杨辉三角

#include<stdio.h> int main() {int x 0; //表示杨辉三角的的大小int y 1;printf("请输入x的值: ");scanf("%d", &x);for (int i 0; i < x; i) {for (int j 0; j < i; j) {if (j 0 || i 0) {y 1;}else {y y * (i - j 1) / j;}pri…...

性能测试-持续测试及性能测试建设(22)

什么是持续测试? 持续测试定义为:在软件交付流水线中执行自动化测试的过程,目的是获得关于预发布软件业务风险的即时反馈。 完成持续测试,我们还是需要回到定义中,它有3个关键词:软件交付流水线、自动化测试、即时反馈。 首先,持续测试需要具备一条完整的流水线,其代表…...

嵌入式C 语言中的三块技术难点

​ C 语言在嵌入式学习中是必备的知识&#xff0c;甚至大部分操作系统都要围绕 C 语言进行&#xff0c;而其中有三块技术难点&#xff0c;几乎是公认级别的“难啃的硬骨头”。 今天就来带你将这三块硬骨头细细拆解开来&#xff0c;一定让你看明白了。 0x01 指针 指针是公认…...

【斗破年番】紫研新形象,萧炎终成翻海印,救援月媚,三宗决战

Hello,小伙伴们&#xff0c;我是小郑继续为大家深度解析斗破年番。 斗破苍穹年番动画更新了&#xff0c;小医仙帅气回归&#xff0c;萧炎紫妍成功进入山谷闭关苦修&#xff0c;美杜莎女王守护没多久&#xff0c;就因蛇人族求救离开。从官方公布的最新预告来看&#xff0c;萧炎紫…...

差分方程模型:国民总收入(GDP)的乘数-加速数模型

【背景知识-凯恩斯经济增长模型】 凯恩斯(John M.Keynes)建立了著名的国民经济增长模型。令Y表示国民总收入&#xff0c;C表示总消费&#xff0c;E为总支出&#xff0c;I表示投资&#xff0c;G为政府的投入&#xff08;如基建等&#xff09;。那么有 【6.1】 其中&#xff0…...

【C语言】指针和数组笔试题解析(1)

指针是C语言的灵魂&#xff0c;他的玩法多种多样&#xff0c;这篇文章带来指针的笔试题详解&#xff0c;可以帮助我们更好的理解与巩固指针的知识 目录 预备知识&#xff1a;题目&#xff1a;一维数组&#xff1a;二维数组&#xff1a; 题目比较多&#xff0c;但切记戒骄戒躁&a…...

Vue中组件的三种注册方式

组件的注册 1.全局注册&#xff1a; 在全局注册中&#xff0c;你需要确保在 Vue 根实例之前导入并注册组件。通常&#xff0c;你会在入口文件&#xff08;例如 main.js&#xff09;中执行这些操作。 // main.jsimport Vue from vue; import App from ./App.vue;// 导入全局组…...

docker 和k8s 入门

docker 和k8s 入门 本文是云原生的学习记录&#xff0c;可以参考以下文档 k8s https://www.yuque.com/leifengyang/oncloud 相关视频教程可参考如下 https://www.bilibili.com/video/BV13Q4y1C7hS?p2&vd_source0882f549dac54045384d4a921596e234 相对于公有云&#x…...

基于Yolov8的交通标志牌(TT100K)识别检测系统

1.Yolov8介绍 Ultralytics YOLOv8是Ultralytics公司开发的YOLO目标检测和图像分割模型的最新版本。YOLOv8是一种尖端的、最先进的&#xff08;SOTA&#xff09;模型&#xff0c;它建立在先前YOLO成功基础上&#xff0c;并引入了新功能和改进&#xff0c;以进一步提升性能和灵活…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...