当前位置: 首页 > 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;以进一步提升性能和灵活…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...