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

算法日记 33 day 动态规划(打家劫舍,股票买卖)

今天来看看动态规划的打家劫舍和买卖股票的问题。

上题目!!!!

题目:打家劫舍

198. 打家劫舍 - 力扣(LeetCode)

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

题目分析:

        对于每一房间其实只有两种状态,偷或不偷,而且这个状态也取决于之前偷没偷。五部曲分析。

dp[i]:小偷到第i间放的最大金额

i的两种状态(偷,不偷)

不偷:dp[i]=dp[i-1]

偷:dp[i]=dp[i-2]

dp[0]=nums[0]    dp[1]=max(nums[0],nums[1])

public class Solution {public int Rob(int[] nums) {if(nums.Length==0) return 0;if(nums.Length==1) return nums[0];int[] dp=new int[nums.Length];dp[0]=nums[0];dp[1]=Math.Max(nums[0],nums[1]);for(int i=2;i<nums.Length;i++){dp[i]=Math.Max(dp[i-2]+nums[i],dp[i-1]);}return dp[nums.Length-1];}
}

 题目:打家劫舍 2

213. 打家劫舍 II - 力扣(LeetCode)

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

题目分析:

        房子围城一圈,那么对于首尾的房子而言,我们只能偷一个,其他的房间呢则尽量偷。本质上就和上一题一样了,无非是偷的时候划分一下区间即可,其他部分完全一样。

public class Solution {public int Rob(int[] nums) {if(nums.Length==0) return 0;if(nums.Length==1) return nums[0];int res1=RobRange(nums,0,nums.Length-2);int res2=RobRange(nums,1,nums.Length-1);return Math.Max(res1,res2);}public int RobRange(int[] nums,int start,int end){if (end == start) return nums[start];int[] dp=new int[nums.Length];dp[start]=nums[start];dp[start+1]=Math.Max(nums[start],nums[start+1]);for(int i=start+2;i<=end;i++){dp[i]=Math.Max(dp[i-2]+nums[i],dp[i-1]);}return dp[end];}
}

题目:打家劫舍 III

 337. 打家劫舍 III - 力扣(LeetCode)

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。

除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。

题目分析: 

        房子的排列变成了树形结构,那么不触发警报意味着,如果我们偷了一个结点,那么他的两个子节点都不能偷。

        其实结点的状态任然是两种偷或者不偷。但是我们要偷取的金额最大,一定要考虑不偷这个的情况下,他的左右子节点偷不偷呢。所以需要将左右孩子的偷不偷的最大金额返回给父节点,那么对于这个树的遍历只能使用后序遍历的方式。

public class Solution {public int Rob(TreeNode root) {int[] res=RobTrue(root);return Math.Max(res[1],res[0]);}public int[] RobTrue(TreeNode root){if(root==null) return new int[2]{0,0};int[] leftDp=RobTrue(root.left);int[] rightDp=RobTrue(root.right);//下标为0记录不偷该节点所得到的的最大金钱,下标为1记录偷该节点所得到的的最大金钱。int res1=root.val+leftDp[0]+rightDp[0];//偷这个结点加上不偷左右孩子的最大值int res2=Math.Max(leftDp[0],leftDp[1])+Math.Max(rightDp[0],rightDp[1]);//不偷这个结点,就考虑左右孩子要不要偷return new int[]{res2,res1};}
}

题目:买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣(LeetCode)

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

题目分析:

        这一题可以用暴力和贪心的方法解决。

暴力,依次枚举股票价格,并且找出最大差值作为结果即可。

贪心的想法很自然就是取最左最小值,取最右最大值,那么得到的差值就是最大利润。

两者差不多。

public class Solution {public int MaxProfit(int[] prices) {int min=int.MaxValue;int res=0;for(int i=0;i<prices.Length;i++){min=Math.Min(prices[i],min);res=Math.Max(res,prices[i]-min);}return res;}
}

动态规划:

        考虑股票的状态,其实就只有持有和不持有两种状态。注意这里的持有和不持有并不是买入卖出的意思。来看看dp数组的解释。

dp[i][0]:在第i天这支股票在我手上持有的最大金额(利润)

dp[i][1]:在第i天这支股票不在我手上持有的最大金额(利润)

注意两个的区别,因为这个持有和不持有他需要考虑前一天的状态,也就是说在这一天之前,这个股票我可能已经买入或者卖出了。这个很重要。

递推公式:

持有股票(1.在这一天之前我就持有了 2,之前我没有,但是今天买入后持有了)

1.dp[i-1][0]   2.-price[i]

 dp[i][0]=max(dp[i-1][0],-price[i])

不持有股票(1.在这一天之前我就没有了 2,之前我有,但是今天卖了后就没有了)

1.dp[i-1][1]   2.dp[i-1][0]+price[i]

 dp[i][0]=max(dp[i-1][1] ,dp[i-1][0]+price[i])

初始化就很好理解了,那么来看看代码

public class Solution {public int MaxProfit(int[] prices) {int[,] dp=new int[prices.Length,2];dp[0,0]=-prices[0];//持有这个股票dp[0,1]=0;//不持有这个股票for(int i=1;i<prices.Length;i++){dp[i,0]=Math.Max(-prices[i],dp[i-1,0]);dp[i,1]=Math.Max(dp[i-1,0]+prices[i],dp[i-1,1]);}return Math.Max(dp[prices.Length-1,0],dp[prices.Length-1,1]);}
}

 题目:买卖股票的最佳时机II

122. 买卖股票的最佳时机 II - 力扣(LeetCode)

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润 。

题目分析:

         注意和上一题的区别,题目中的每一天意味着我可以多次买入卖出。但是上一题我只能操作一次。

        这里的dp的含义和上一题一样的,区别是dp的递推公式。

递推公式:

持有股票(1.在这一天之前我就持有了 2,(可能我已经卖出过了)之前我没有,但是今天买入后持有了)

1.dp[i-1][0]   2.dp[i-1][1]-price[i](上一天是不持有的状态)

 dp[i][0]=max(dp[i-1][0],dp[i-1][1]-price[i])

不持有股票(1.在这一天之前我就没有了 2,之前我有,但是今天卖了后就没有了)

1.dp[i-1][1]   2.dp[i-1][0]+price[i]

 dp[i][0]=max(dp[i-1][1] ,dp[i-1][0]+price[i])

public class Solution {public int MaxProfit(int[] prices) {int[,] dp=new int[prices.Length,2];dp[0,0]=-prices[0];//持有这个股票dp[0,1]=0;//不持有这个股票for(int i=1;i<prices.Length;i++){dp[i,0]=Math.Max(dp[i-1,1]-prices[i],dp[i-1,0]);dp[i,1]=Math.Max(dp[i-1,0]+prices[i],dp[i-1,1]);}return Math.Max(dp[prices.Length-1,0],dp[prices.Length-1,1]);}
}

 主要区别在于持有股票是需要考虑之前是否有卖出过,这一点在下面的题中很重要

题目:买卖股票的最佳时机III

123. 买卖股票的最佳时机 III - 力扣(LeetCode)

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

 题目分析:

        会看前面两题,第一题要求只能买入卖出1次,第二题能买入卖出无数次。而这一题最多两次,和上面两题一样,看看股票在第i天可能出现的状态。

第一次买入

第一次卖出

第二次买入

第二次卖出

那么dp数组的含义就很好理解了。

来看看递推公式,本质上和上面的题是一样的,无非就是买入卖出的时候需要考虑之前的状态,这一点和第二题一样。

达到dp[i][1]状态,有两个具体操作:

  • 操作一:第i天买入股票了,那么dp[i][1] = dp[i-1][0] - prices[i]
  • 操作二:第i天没有操作,而是沿用前一天买入的状态,即:dp[i][1] = dp[i - 1][1]

那么dp[i][1]究竟选 dp[i-1][0] - prices[i],还是dp[i - 1][1]呢?

一定是选最大的,所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作:

  • 操作一:第i天卖出股票了,那么dp[i][2] = dp[i - 1][1] + prices[i]
  • 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:dp[i][2] = dp[i - 1][2]

所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

同理可推出剩下状态部分:

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]);

对于初始化而言,需要注意的是你可以在一天内多次买入卖出,因为price的长度可以为1。 

public class Solution {public int MaxProfit(int[] prices) {int[,] dp=new int[prices.Length,5];dp[0,0]=0;//0,不操作dp[0,1]=-prices[0];//1,第一次持有dp[0,2]=0;//2,第一次不持有dp[0,3]=-prices[0];//3,第二次持有dp[0,4]=0;//4,第二次不持有for(int i=1;i<prices.Length;i++){dp[i,1]=Math.Max(dp[i-1,1],-prices[i]);dp[i,2]=Math.Max(dp[i-1,1]+prices[i],dp[i-1,2]);dp[i,3]=Math.Max(dp[i-1,3],dp[i,2]-prices[i]);dp[i,4]=Math.Max(dp[i-1,4],dp[i-1,3]+prices[i]);}return Math.Max(dp[prices.Length-1,4],dp[prices.Length-1,2]);}
}

 

对于更详细的解析与其他语言的代码块,可以去代码随想录上查看。

代码随想录 (programmercarl.com)

已刷题目:110

相关文章:

算法日记 33 day 动态规划(打家劫舍,股票买卖)

今天来看看动态规划的打家劫舍和买卖股票的问题。 上题目&#xff01;&#xff01;&#xff01;&#xff01; 题目&#xff1a;打家劫舍 198. 打家劫舍 - 力扣&#xff08;LeetCode&#xff09; 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金…...

JavaScript的let、var、const

这张图片主要介绍了JavaScript中的三种变量声明方式&#xff1a;let、var和const。 1. let 含义&#xff1a;let是现在实际开发中常用的变量声明方式。特点&#xff1a; 块级作用域&#xff1a;let声明的变量只在其所在的块级作用域内有效。例如&#xff1a;{let x 10; } co…...

C语言-数学基础问题

一.奇数、偶数问题 1.从键盘上输入一个整数&#xff0c;判断并输出它是奇数还是偶数。 //从键盘上输入一个整数&#xff0c;判断并输出它是奇数还是偶数。 main() {int i;printf("输入一个整数:\n");scanf("%d",&i);if(i%20)printf("它是偶数\n…...

解决单元测试时找不到类名

场景&#xff1a; springboot单元测试mockito对mapper进行mock时&#xff1a; tk.mybatis.mapper.mapperexception: 无法获取实体类 XX.xx 对应的表名 分析&#xff1a; 使用了一个方法&#xff1a;Example examplenew Example(User.class); 进入源码后发现Entityhelper没…...

从零开始-VitePress 构建个人博客上传GitHub自动构建访问

从零开始-VitePress 构建个人博客上传GitHub自动构建访问 序言 VitePress 官网&#xff1a;VitePress 中文版 1. 什么是 VitePress VitePress 是一个静态站点生成器 (SSG)&#xff0c;专为构建快速、以内容为中心的站点而设计。简而言之&#xff0c;VitePress 获取用 Markdown…...

【案例学习】如何使用Minitab实现包装过程的自动化和改进

Masimo 是一家全球性的医疗技术公司&#xff0c;致力于开发和生产各种行业领先的监控技术&#xff0c;包括创新的测量、传感器和患者监护仪。在 Masimo Hospital Automation 平台的助力下&#xff0c;Masimo 的连接、自动化、远程医疗和远程监控解决方案正在改善医院内外的护理…...

【ArcGISPro】使用AI提取要素-土地分类(sentinel2)

Sentinel2数据处理 【ArcGISPro】Sentinel-2数据处理-CSDN博客 土地覆盖类型分类 处理结果...

深度解析:Nginx模块架构与工作机制的奥秘

文章目录 前言Nginx是什么?Ngnix特点&#xff1a; 一、Nginx模块与工作原理1.Nginx的模块1.1 Nginx模块常规的HTTP请求和响应的流程图:1.2 Nginx的模块从结构上分为如下三类&#xff1a;1.3 Nginx的模块从功能上分为如下三类: 2.Nginx的进程模型2.1 Nginx进程结构2.2 nginx进程…...

分布式kettle调度平台v6.4.0新功能介绍

介绍 Kettle&#xff08;也称为Pentaho Data Integration&#xff09;是一款开源的ETL&#xff08;Extract, Transform, Load&#xff09;工具&#xff0c;由Pentaho&#xff08;现为Hitachi Vantara&#xff09;开发和维护。它提供了一套强大的数据集成和转换功能&#xff0c…...

企业数字化转型现状

国家数字经济战略背景 2018年以来&#xff0c;国家政府不断出台政策规范我国企业数字化治理市场。2018年9月颁布《关于发展数字经济稳定并扩大就业的指导意见》&#xff0c;支持建设一批数字经济创新创业孵化机构。积极推进供应链创新与应用&#xff0c;支持构建以企业为主导。…...

极客大挑战2024wp

极客大挑战2024wp web 和misc 都没咋做出来&#xff0c;全靠pwn✌带飞 排名 密码学和re没做出几个&#xff0c;就不发了 web ez_pop 源代码 <?php Class SYC{public $starven;public function __call($name, $arguments){if(preg_match(/%|iconv|UCS|UTF|rot|quoted…...

将django+vue项目发布部署到服务器

1.部署django后端服务 部署架构 1.1 下载依赖插件 pip3.8 freeze > requirements.txt1.2 安装依赖插件 pip3 install -r requirements.txt1.3 安装mysql数据库 apt install mysql-server初始化数据库 CREATE USER admin% IDENTIFIED WITH mysql_native_password BY 123…...

函数类型注释和Union联合类型注释

函数类型注释格式&#xff08;调用时提示输入参数的类型&#xff09;: )def 函数名(形参名:类型&#xff0c;形参名:类型&#xff09;->函数返回值类型: 函数体 Union联合类型注释&#xff08;可注释多种类型混合的变量&#xff09;格式: #先导入模块 from typing import…...

python画图|无坐标轴自由划线操作fig.add_artist(lines.Line2D()函数

【1】引言 新发现了一种自由划线操作函数&#xff0c;和大家共享。 【2】官网教程 点击下述代码&#xff0c;直达官网&#xff1a; https://matplotlib.org/stable/gallery/misc/fig_x.html#sphx-glr-gallery-misc-fig-x-py 官网代码非常简洁&#xff0c;我进行了解读。 …...

MacOS系统上Jmeter 录制脚本遇到的证书坑位

一、JMeter介绍与安装 1&#xff0c;下载及安装 jmeter官网地址 二、录制百度链接https请求时&#xff0c;需要导入jmeter相关证书到macos系统的更目录中. 导入方式&#xff0c;直接拖入mac的系统中&#xff0c;始终新人就可以&#xff1b; 三、jmeter 创建相关的录制组件…...

网络层协议IP

对于网络层我们直接通过IP协议来了解其内容 一.IP协议 首先我们先来了解几个概念&#xff1a; 主机&#xff1a;配有IP地址&#xff0c;但是不进行路由控制的设备 路由器&#xff1a;配有IP地址&#xff0c;同时进行路由控制的设备 节点&#xff1a;主机和路由器的统称 所以现在…...

《硬件架构的艺术》笔记(七):处理字节顺序

介绍 本章主要介绍字节顺序的的基本规则。&#xff08;感觉偏软件了&#xff0c;不知道为啥那么会放进《硬件架构的艺术》这本书&#xff09;。 定义 字节顺序定义数据在计算机系统中的存储格式&#xff0c;描述存储器中的MSB和LSB的位置。对于数据始终以32位形式保存在存储器…...

反向代理模块

1 概念 1.1 反向代理概念 反向代理是指以代理服务器来接收客户端的请求&#xff0c;然后将请求转发给内部网络上的服务器&#xff0c;将从服务器上得到的结果返回给客户端&#xff0c;此时代理服务器对外表现为一个反向代理服务器。 对于客户端来说&#xff0c;反向代理就相当于…...

风尚云网前端学习:一个简易前端新手友好的HTML5页面布局与样式设计

风尚云网前端学习&#xff1a;一个简易前端新手友好的HTML5页面布局与样式设计 简介 在前端开发的世界里&#xff0c;HTML5和CSS3是构建现代网页的基石。本文将通过一个简单的HTML5页面模板&#xff0c;展示如何使用HTML5的结构化元素和CSS3的样式特性&#xff0c;来创建一个…...

spacy 安装 en_core_web_sm

目录 spacy win11 成功 linux No matching distribution found for numpy<3.0.0,>2.0.0 解决方法&#xff1a; linux安装失败&#xff1a; linux安装成功 从GitHub上下载 spacy win11 成功 pip install -i https://pypi.tuna.tsinghua.edu.cn/simple spacy linux N…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...