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

算法日记 33 day 动态规划（打家劫舍，股票买卖）

news 来源：原创 2025/7/20 11:15:45

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

上题目！！！！

题目：打家劫舍

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 动态规划（打家劫舍，股票买卖）

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

编程日记 2025/7/20 11:15:45

从零开始打造个人博客：我的网页设计之旅

✅作者简介：2022年博客新星第八。热爱国学的Java后端开发者，修心和技术同步精进。 🍎个人主页：Java Fans的博客 🍊个人信条：不迁怒，不贰过。小知识，大智慧。 ✨特色专栏&#xff1a…...

编程日记 2025/7/20 7:04:35

用python将一个扫描pdf文件改成二值图片组成的pdf文件

使用墨水屏读书现在似乎越来越流行，这确实有一定的好处，例如基本不发热，电池续航时间超长，基本不能游戏所以有利于沉浸式阅读，还有不知道是不是真的有用的所谓防蓝光伤害。但是，如果阅读的书籍是扫描图片组…...

编程日记 2025/7/20 11:03:29

Electron开发构建工具electron-vite(alex8088)添加VueDevTools(VitePlugin)

零、介绍本文章的electron-vite指的是这个项目👉electron-vite仓库，electron-vite网站本文章的VueDevTools指的是VueDevTools的Vite插件版👉https://devtools.vuejs.org/guide/vite-plugin 一、有一个用electron-vite创建的项目略二、…...

编程日记 2025/7/15 8:59:16

服务器数据恢复—raid5阵列热备盘上线失败导致EXT3文件系统不可用的数据恢复案例

服务器数据恢复环境： 两组分别由4块SAS硬盘组建的raid5阵列，两组阵列划分的LUN组成LVM架构，格式化为EXT3文件系统。服务器故障： 一组raid5阵列中的一块硬盘离线。热备盘自动上线替换离线硬盘，但在热备盘上线同步数据…...

编程日记 2025/7/9 19:11:03

网络安全基础——网络安全法

填空题 1.根据**《中华人民共和国网络安全法》**第二十条(第二款)，任何组织和个人试用网路应当遵守宪法法律，遵守公共秩序，遵守社会公德，不危害网络安全，不得利用网络从事危害国家安全、荣誉和利益，煽动颠…...

编程日记 2025/7/20 11:15:44

go-rod vs Selenium：自动化测试工具的比较与选择

自动化测试是软件开发过程中的关键环节，它能够帮助我们发现缺陷、验证功能并提高软件质量。随着Web技术的快速发展，市场上出现了多种自动化测试工具，其中Selenium和go-rod是两个备受关注的选择。本文将从多个维度对这两个工具进行比较&#x…...

编程日记 2025/7/19 20:03:59

Ubuntu20.04+ROS 进行机械臂抓取仿真：环境搭建（一）

目录一、从官网上下载UR机械臂二、给UR机械臂添加夹爪三、报错解决本文详细介绍如何在Ubuntu20.04ROS环境中为Universal Robots的UR机械臂添加夹爪。首先从官方和第三方源下载必要的软件包，包括UR机械臂驱动、夹爪插件和相关依赖。然后，针对gazeb…...

编程日记 2025/7/19 4:56:34

Pytorch微调深度学习模型

在公开数据训练了模型，有时候需要拿到自己的数据上微调。今天正好做了一下微调，在此记录一下微调的方法。用Pytorch还是比较容易实现的。网上找了很多方法，以及Chatgpt也给了很多方法，但是不够简洁和容易理解。大体步骤是&…...

编程日记 2025/7/16 20:38:40

PPT分享 | IBM集团业务流程架构顶层规划-订单到交付-销售到回款方案

PPT下载链接见文末~ IBM业务流程规划方法是一套结构化、体系化的流程设计理论，其企业流程框架（EPF）是一种用于企业业务流程架构设计梳理的方法论。一、IBM业务流程规划方法的核心 IBM的BPM（业务流程管理）流程管理体…...

编程日记 2025/7/20 11:14:27

后端并发编程操作简述 Java高并发程序设计六类并发容器七种线程池四种阻塞队列

目录并发集合 1. ConcurrentHashMap： 2. CopyOnWriteArrayList： 3. CopyOnWriteArraySet： 4. BlockingQueue系列： 5. ConcurrentSkipListMap 和 ConcurrentSkipListSet： 6. ConcurrentLinkedDeque：…...

编程日记 2025/7/20 10:59:50

基于LLama_factory的Qwen2.5大模型的微调笔记

Qwen2.5大模型微调记录 LLama-facrotyQwen2.5 模型下载。huggingface 下载方式Modelscope 下载方式数据集准备模型微调模型训练模型验证及推理模型导出部署推理vllm 推理Sglang 推理 LLama-facroty 根据git上步骤安装即可，要求的软硬件都装上。 llama-factory运行…...

编程日记 2025/7/11 19:13:29

resnet50,clip，Faiss+Flask简易图文搜索服务

一、实现文件夹目录结构： templates -----upload.html faiss_app.py 前端代码： <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widt…...

编程日记 2025/7/20 11:06:46

亚信安全与飞书达成深度合作

近日，亚信安全联合飞书举办的“走近先进”系列活动正式走进亚信。活动以“安全护航信息化共筑数字未来路”为主题，吸引了众多数字化转型前沿企业的近百位领导参会。作为“走近先进”系列的第二场活动，本场活动更加深入挖掘了数字化转型的基础…...

编程日记 2025/7/19 8:14:09

Spring框架特性及包下载（Java EE 学习笔记04）

1 Spring 5的新特性 Spring 5是Spring当前最新的版本，与历史版本对比，Spring 5对Spring核心框架进行了修订和更新，增加了很多新特性，如支持响应式编程等。更新JDK基线因为Spring 5代码库运行于JDK 8之上，所以Spri…...

编程日记 2025/7/15 23:44:40

C# 使用HangFire 第一章：.net Framework 4.6 WebAPI 使用Hangfire 第二章：net 8使用hangfire实现库存同步任务文章目录 C# 使用HangFire前言项目源码一、项目架构二、项目服务介绍HangFire服务结构解析HangfireCollectionExtensions 类ModelHangfireSettingsHttpAuthInfoUs…...

编程日记 2025/7/19 15:44:11

python VS c++

一、语法特点 Python： 语法简洁、优雅，代码可读性极强，采用缩进来表示代码块，摒弃了像 C 那样使用大括号的传统方式，使得代码看上去十分清晰简洁。例如： if 5 > 3:print("5大于3") elif 5 …...

编程日记 2025/7/14 11:05:12

windows C#-属性

属性提供了一种将元数据或声明性信息与代码(程序集、类型、方法、属性等)关联的强大方法。将属性与程序实体关联后，可以使用称为反射的技术在运行时查询该属性。属性具有以下属性： 属性将元数据添加到您的程序中。元数据是有关程序中定义的类型的信息…...

编程日记 2025/7/19 13:58:41

Redis常见面试题总结(上)

Redis 基础什么是 Redis？ Redis （REmote DIctionary Server）是一个基于 C 语言开发的开源 NoSQL 数据库（BSD 许可）。与传统数据库不同的是，Redis 的数据是保存在内存中的（内存数据库&#xf…...

编程日记 2025/7/19 16:45:00

小鹏汽车智慧材料数据库系统项目总成数据同步

1、定时任务处理 2、提供了接口小鹏方面提供的推送的数据表结构： 这几个表总数为100多万，经过条件筛选过滤后大概2万多条数据小鹏的人给的示例图： 界面： SQL: -- 查询车型 select bmm.md_material_id, bmm.material_num, bm…...

编程日记 2025/7/12 1:47:38

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

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

编程日记 2025/7/15 20:21:49

论文阅读：A fast, scalable and versatile tool for analysis of single-cell omics data

Zhang, K., Zemke, N.R., Armand, E.J. et al. A fast, scalable and versatile tool for analysis of single-cell omics data. Nat Methods 21, 217–227 (2024). 论文地址：https://doi.org/10.1038/s41592-023-02139-9 代码地址：https://github.com…...

编程日记 2025/7/19 12:54:51

【从零开始的LeetCode-算法】43. 网络延迟时间

有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过有向边的传递时间。 times[i] (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。现在，…...

编程日记 2025/7/16 5:24:45

一文理解 Python 编程语言中的 .strip() 方法

🍉 CSDN 叶庭云：https://yetingyun.blog.csdn.net/ Python 中的 strip() 方法：初学者友好指南在 Python 中，strip() 是一个极为实用的字符串方法，主要用于移除字符串首尾的特定字符。默认情况下，它会清除…...

编程日记 2025/7/19 23:26:03

solr 远程命令执行 (CVE-2019-17558)

漏洞描述 Apache Velocity是一个基于Java的模板引擎，它提供了一个模板语言去引用由Java代码定义的对象。Velocity是Apache基金会旗下的一个开源软件项目，旨在确保Web应用程序在表示层和业务逻辑层之间的隔离（即MVC设计模式）。 Apa…...

编程日记 2025/7/16 15:25:33

【cocos creator】下拉框

https://download.csdn.net/download/K86338236/90038176 const { ccclass, property } cc._decorator;type DropDownOptionData {optionString?: string,optionSf?: cc.SpriteFrame } type DropDownItemData {label: cc.Label,sprite: cc.Sprite,toggle: cc.Toggle }cccl…...

编程日记 2025/7/9 7:40:06

题目：打家劫舍

题目分析：

题目：打家劫舍 2

题目分析：

题目：打家劫舍 III

题目分析：

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

题目分析：

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

题目分析：

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

题目分析：

已刷题目：110

相关文章：