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

代码随想录day49:动态规划part10

121.买卖股票的最佳时机

贪心:

class Solution {
public:int maxProfit(vector<int>& prices) {int low = INT_MAX;int result = 0;for (int i = 0; i < prices.size(); i++) {low = min(low, prices[i]);  // 取最左最小价格result = max(result, prices[i] - low); // 直接取最大区间利润}return result;}
};

动态规划:
1.dp数组的定义–dp[i][0]表示第i天持有股票所得最多现金,dp[i][1]表示第i天不持有股票所得最多现金。注意持有不等于第i天买入。
2.递推公式:
dp[i][0] = max(dp[i - 1][0], -prices[i])第i天持有股票可能是前一天就持有股票,也可能是今天刚买的股票
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);第i天不持有股票可能是昨天卖出的,也可能是今天卖出的。
3.dp数组初始化:其基础都是要从dp[0][0]和dp[0][1]推导出来。
第0天就持有股票,则就是第0天买入的。dp[0][0]=-price[0];
第0天不持有股票,则还没开始买股票,dp[0][1]=0;
4.遍历顺序:从前向后遍历。

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

优化:从递推公式可以看出,dp[i]只是依赖于dp[i - 1]的状态。那么我们只需要记录 当前天的dp状态和前一天的dp状态就可以了,可以使用滚动数组来节省空间:

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

买卖股票的最佳时机II

与上一道题的区别:可以多次买卖一支股票,但必须在再次购买前出售掉之前的股票
之前的贪心算法就用的这个例子讲的
在这里插入图片描述这次动态规划的方法:
1.dp数组的定义:dp[i][0] 表示第i天持有股票所得现金。dp[i][1] 表示第i天不持有股票所得最多现金
2.递推公式:
dp[i][0] = max(dp[i - 1][0], dp[i-1][1]-prices[i])第i天持有股票可能是前一天就持有股票,也可能是今天刚买的股票
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);第i天不持有股票可能是昨天卖出的,也可能是今天卖出的。
3.dp数组初始化:其基础都是要从dp[0][0]和dp[0][1]推导出来。
第0天就持有股票,则就是第0天买入的。dp[0][0]=-price[0];
第0天不持有股票,则还没开始买股票,dp[0][1]=0;
4.遍历顺序:从前向后遍历。

        vector<vector<int>> dp(2,vector<int>(2,0));dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<prices.size();i++){dp[i%2][0]=max(dp[(i-1)%2][0],dp[(i-1)%2][1]-prices[i]);//dp[i-1][1]-pricesdp[i%2][1]=max(dp[(i-1)%2][1],dp[(i-1)%2][0]+prices[i]);}return dp[(prices.size()-1)%2][1];

相关文章:

代码随想录day49:动态规划part10

121.买卖股票的最佳时机 贪心&#xff1a; class Solution { public:int maxProfit(vector<int>& prices) {int low INT_MAX;int result 0;for (int i 0; i < prices.size(); i) {low min(low, prices[i]); // 取最左最小价格result max(result, prices[i…...

fofa搜索使用

fofa搜索使用 文章目录 fofa搜索使用网站fofa搜索语法多条件查询 网站fofa https://fofa.info/搜索语法 1.title”beijing”从标题中搜索“北京2.headerQ"thinkphp”从http响应头中搜索“thinkphp3.body”管理后台”从html正文中搜索“管理后台4.domain”163.com”从子域…...

husky+lint-staged+eslint+prettier+stylelint+commitlint

概念: husky,暴露出git的hook钩子,在这些钩子执行一些命令,lint-staged,只在git的暂存区有修改的文件进行lint操作,执行一些校验脚本eslint,prettier,styelint有npm包还有对应的scode插件,其中npm包是用于执行那些诸如入eslint --fix "src/**/*.{js,jsx,…}"的脚本命…...

图像处理与计算机视觉--第四章-图像滤波与增强-第一部分

目录 1.灰度图亮度调整 2.图像模板匹配 3.图像裁剪处理 4.图像旋转处理 5.图像邻域与数据块处理 学习计算机视觉方向的几条经验: 1.学习计算机视觉一定不能操之过急&#xff0c;不然往往事倍功半&#xff01; 2.静下心来&#xff0c;理解每一个函数/算法的过程和精髓&…...

【go】字符串切片与字符串出入数据库转化

文章目录 需求代码入库出库 需求 将请求数据存入数据库与从数据库读取数据返回在出库不使用反序列化情况下 请求结构体 type NoticegroupsCreateReq struct {Name string json:"name" binding:"required"UserIds []string json:"user_ids…...

Redis中是如何实现分布式锁的?

分布式锁常见的三种实现方式&#xff1a; 数据库乐观锁&#xff1b; 基于Redis的分布式锁&#xff1b; 基于ZooKeeper的分布式锁。 本次面试考点是&#xff0c;你对Redis使用熟悉吗&#xff1f;Redis中是如何实现分布式锁的。 要点 Redis要实现分布式锁&#xff0c;以下条件应…...

似然和概率

前言 高斯在处理正态分布的首次提出似然&#xff0c;后来英国物理学家&#xff0c;费歇尔 概率是抛硬币之前&#xff0c;根据环境推断概率 似然则相反&#xff0c;根据结果推论环境 P是关于x的函数&#xff0c;比如x为正面朝上的结果&#xff0c;或者反面朝上的结果&#xf…...

php代码审计篇熊海cms代码审计

文章目录 自动审计逐个分析首页index.php文件包含漏洞后台逻辑漏洞cookie绕过登录后台sql报错注入存储型XSS 结束吧 自动审计 看到有很多 逐个分析 首页index.php文件包含漏洞 读一下代码&#xff0c;可以看到很明显的一个文件包含 <?php //单一入口模式 error_repor…...

Android Camera2获取摄像头的视场角(FOV)信息

一、概念 FOV&#xff08;Field of View&#xff09;是一个用于描述视野范围的术语。它通常用于计算设备&#xff08;如摄像机、虚拟现实头显或眼睛&#xff09;所能捕捉到的可见区域。 水平FOV&#xff08;Horizontal FOV&#xff09;&#xff1a;描述视野在水平方向上的范围…...

服务接口调用OpenFeign_日志增强

OpenFeign虽然提供了日志增强功能&#xff0c;但是默认是不显示任何日志的&#xff0c;不过开发者在调试阶段可以自己配置日志的级别。 OpenFeign的日志级别如下&#xff1a; NONE&#xff1a;默认的&#xff0c;不显示任何日志;BASIC&#xff1a;仅记录请求方法、URL、响应状…...

ADC数模转化器

简介 • ADC &#xff08; Analog-Digital Converter &#xff09;模拟 - 数字转换器 • ADC 可以将引脚上连续变化的模拟电压转换为内存中存储的数字变量&#xff0c;建立模拟电路到数字电路的桥梁 • 12 位逐次逼近型 ADC &#xff0c; 1us 转换时间 &#xff08;12位:分辨率…...

Linux DataEase数据可视化分析工具结合cpolar实现远程访问

文章目录 前言1. 安装DataEase2. 本地访问测试3. 安装 cpolar内网穿透软件4. 配置DataEase公网访问地址5. 公网远程访问Data Ease6. 固定Data Ease公网地址 前言 DataEase 是开源的数据可视化分析工具&#xff0c;帮助用户快速分析数据并洞察业务趋势&#xff0c;从而实现业务…...

使用JAXB将xml转成Java对象

文章目录 使用JAXB将xml转成Java对象1. xml内容2. Java对象类3. 封装的工具类4. 测试 使用JAXB将xml转成Java对象 工作中遇到个问题&#xff0c;需要将xml转对象&#xff0c;之前复杂的xml都是自己用dom4j来解析组装成Java对象&#xff0c;但是对于简单的&#xff0c;看到了JAX…...

第6讲:v-for使用

目录 1.循环遍历 2.v-for遍历整形变量&#xff08;99乘法表&#xff09; 3.v-for遍历普通数组 4.v-for遍历数组对象 1.循环遍历 v-for指令基于一个数组渲染一个列表&#xff0c;它和JavaScript的遍历语法相似&#xff1a; v-for”item in list” list 是一个数组&#xff0c; i…...

ubuntu http 服务器响应

代码&#xff1a; h文件 #include <iostream> #include <curl/curl.h>#include <net/if.h> #include <sys/ioctl.h> #include <arpa/inet.h> #include <string.h>#include <event.h> #include <event2/http.h> #include <…...

C语言 结构体位域

在C语言中&#xff0c;结构体位域是一种特殊的结构体成员&#xff0c;它允许在结构体中定义一个二进制位字段&#xff0c;以便在单个字节中存储多个布尔值或枚举值。 结构体位域的定义方式如下&#xff1a; struct { unsigned int bit1: 1; // 定义一个名为bit1的位域&…...

ChatGPT AIGC 非常实用的AI工具集合大全

实战AI 工具箱 AIGC ChatGPT 职场案例60集, Power BI 商业智能 68集, 数据库Mysql8.0 54集 数据库Oracle21C 142集, Office, Python ,ETL Excel 2021 实操,函数,图表,大屏可视化 案例实战 http://t.csdn.cn/zBytu...

Visual Studio Cpp CLR C# 替换

1、首先将文件中所有都替换 你需要的名字 替换为整个解决方案 2、新建工程取名 Laserbeam_upper 3、把原工程下的cpp放进来&#xff0c;并改名Laserbeam_upper 4、在这里逐步添加 属性表配置opencv 5、cpp需要修改的两个地方 6、CLR新建和添加 选类库新建、然后直接粘贴进来…...

typeorm利用mongodb,save的时候更新会出现重复数据的问题。

是因为mongodb把new Object当成插入的数据了&#xff0c;修正方案 ObjectIdColumn({name: _id,})Transform((value) > new ObjectId(value.obj._id.toString()))// ts-ignore_id: ObjectId;Transform((value) > new ObjectId(value.obj._id.toString()))转换下就好了。...

决策树案例分析

决策树(Decision Tree)常用于研究类别归属和预测关系的模型&#xff0c;比如是否抽烟、是否喝酒、年龄、体重等4项个人特征可能会影响到‘是否患癌症’&#xff0c;上述4项个人特征称作‘特征’&#xff0c;也即自变量&#xff08;影响因素X&#xff09;&#xff0c;‘是否患癌…...

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

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

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

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

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

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...