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

代码随想录算法训练营第五十天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III

代码随想录算法训练营第五十天

198.打家劫舍

题目链接:198.打家劫舍

  1. 确定dp数组以及下标的含义:dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。
  2. 确定递推公式:max(dp[i - 1], dp[i - 2] + nums[i]);,不偷当前节点和偷当前节点哪个获利最大就取哪个
  3. dp数组如何初始化:dp[0]=nums[0],只有一个必须偷。dp[1]=max(nums[0],nums[1])一共2个元素,只能偷一个最大的
  4. 确定遍历顺序:从前向后遍历。
  5. 打印dp数组。
class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 1)return nums[0];vector<int> dp(nums.size(), 0);dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[nums.size() - 1];}
};

213.打家劫舍II

题目链接:213.打家劫舍II
偷第一家就不能偷最后一家,偷最后一家就不能偷第一家,分别将两种状态求出,再从二者之间找最大值。两种情况分别可以用上题方法求解。

class Solution {
public:int Rob(vector<int>& nums,int start, int end){if(start==end)return nums[start];vector<int> dp(nums.size(), 0);dp[start] = nums[start];dp[start+1] = max(nums[start], nums[start+1]);for (int i = start+2; i <= end; i++) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[end];}int rob(vector<int>& nums) {if(nums.size()==1)return nums[0];int first = Rob(nums,0,nums.size()-2);int last = Rob(nums, 1, nums.size()-1);return max(first,last);}
};

337.打家劫舍III

题目链接:337.打家劫舍III
dp数组表示,每个节点偷当前节点和不偷当前节点可以取得的最大价值。要求当前节点值需要知道左右节点的值,所以是后序遍历。最后再偷根节点和不偷根节点之间取一个最大值即可。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> Rob(TreeNode* cur){if(cur==nullptr)return {0,0};vector<int> left = Rob(cur->left);vector<int> right = Rob(cur->right);vector<int>dp(2);//定义一个dp数组dp[0]表示当前节点不偷可以获得的最大金币,dp[1]表示偷当前节点可以获得的最大金币dp[0] = max(left[0],left[1])+max(right[0],right[1]);//不偷当前节点,那它的子节点可以选择偷或者不偷,左子偷不偷选最大的+右子偷不偷选最大的dp[1] = left[0]+right[0]+cur->val;//偷当前节点,左右子都不能偷,所以等于左不偷+右不偷+当前节点的值return dp;}int rob(TreeNode* root) {return max(Rob(root)[0],Rob(root)[1]);}
};

相关文章:

代码随想录算法训练营第五十天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III

代码随想录算法训练营第五十天 198.打家劫舍 题目链接&#xff1a;198.打家劫舍 确定dp数组以及下标的含义&#xff1a;dp[i]&#xff1a;考虑下标i&#xff08;包括i&#xff09;以内的房屋&#xff0c;最多可以偷窃的金额为dp[i]。确定递推公式&#xff1a;max(dp[i - 1],…...

VB.net 进行CAD二次开发(二)

利用参考文献2&#xff0c;添加面板 执行treeControl New UCTreeView()时报一个错误&#xff1a; 用户代码未处理 System.ArgumentException HResult-2147024809 Message控件不支持透明的背景色。 SourceSystem.Windows.Forms StackTrace: 在 System.Windows…...

安徽某高校数据挖掘作业6

1 根据附件中year文件&#xff0c;编辑Python程序绘制年销售总额分布条形图和年净利润分布条形图&#xff0c;附Python程序和图像。 2 根据附件中quarter和quarter_b文件&#xff0c;编辑Python程序绘制2018—2020年销售额和净利润折线图&#xff0c;附Python程序和图像。 3 …...

CMakeLists.txt和Package.xml

CMakeLists.txt和Package.xml CMakeLists.txt 总览 CMakeLists.txt 是用于定义如何构建 ROS (Robot Operating System) 包的 CMake 脚本文件。CMake 是一个跨平台的构建系统&#xff0c;用于自动化编译过程。在 ROS 中&#xff0c;CMakeLists.txt 文件指定了如何编译代码和链…...

Debian常用命令详解

Debian常用命令详解 Debian是一个流行的Linux发行版&#xff0c;它以其稳定性、强大的包管理系统和丰富的软件仓库而著称。对于Debian用户来说&#xff0c;掌握一些常用的命令行工具和命令是日常系统管理和维护的基础。下面&#xff0c;我们将介绍一些Debian系统中常用的命令。…...

代码随想录算法训练营day29|491.递增子序列、46.全排列、47.全排列II

递增子序列 491. 非递减子序列 - 力扣&#xff08;LeetCode&#xff09; 非递减子序列&#xff0c;则答案的子集中&#xff0c;需保持下一个元素大于等于前一个元素的顺序&#xff0c;由于题目中指出&#xff0c;所有的子序列长度需大于等于2&#xff0c;考虑当条件为path.siz…...

【ARM Cache 与 MMU 系列文章 7.8 – ARMv8/v9 MMU Table 表分配原理及其代码实现 2】

请阅读【ARM Cache 及 MMU/MPU 系列文章专栏导读】 及【嵌入式开发学习必备专栏】 文章目录 MMU Table 表分配原理及其代码实现MMU Table 分配代码实现MMU Table 表分配原理及其代码实现 在做映射的时候所映射的地址范围最大只能是某一级 level table 中 entry 所能支持的最大…...

SAP PP学习笔记17 - MTS(Make-to-Stock) 按库存生产(策略70)

上几章讲了几种策略&#xff0c;策略10&#xff0c;11&#xff0c;30&#xff0c;40。 SAP PP学习笔记14 - MTS&#xff08;Make-to-Stock) 按库存生产&#xff08;策略10&#xff09;&#xff0c;以及生产计划的概要-CSDN博客 SAP PP学习笔记15 - MTS&#xff08;Make-to-St…...

网页音频提取在线工具有哪些 网页音频提取在线工具下载

别再到处去借会员账号啦。教你一招&#xff0c;无视版权和地区限制&#xff0c;直接下载网页中的音频文件。没有复杂的操作步骤&#xff0c;也不用学习任何代码。只要是网页中播放的音频文件&#xff0c;都可以把它下载到本地保存。 一、网页音频提取在线工具有哪些 市面上的…...

【ARM Cache 系列文章 2.1 -- Cache PoP 及 PoDP 介绍】

请阅读【ARM Cache 及 MMU/MPU 系列文章专栏导读】 及【嵌入式开发学习必备专栏】 文章目录 PoP 及 PoDPCache PoDPCache PoP应用和影响PoP 及 PoDP Cache PoDP 点对深度持久性(Point of Deep Persistence, PoDP)是内存系统中的一个点,在该点达到的任何写操作即使在系统供电…...

一文了解JVM面试篇(上)

Java内存区域 1、如何解释 Java 堆空间及 GC? 当通过 Java 命令启动 Java 进程的时候,会为它分配内存。内存的一部分用于创建 堆空间,当程序中创建对象的时候,就从对空间中分配内存。GC 是 JVM 内部的一 个进程,回收无效对象的内存用于将来的分配。 2、JVM 的主要组成…...

C#WPF控件Textbox绑定浮点型数据限制小数位方法

本文讲解C#WPF控件Textbox绑定浮点型数据限制小数位方法。 XAML中,使用StringFormat来格式化TextBox的文本 <Window x:Class="WpfApp.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.m…...

mysql引入表名称的注意事项

1、遇到问题 mapper中的文件是这样的 解析出来的sql是这样的 sql显示为&#xff1a;select * from ‘tableName’ 2、解决方法 mapper文件种使用${tableName}而不是#{tableName}...

C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍

文章目录 前言一、快速排序非递归二、归并排序五、归并排序非递归总结 前言 C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍 一、快速排序非递归 快速排序非递归的定义 快速排序非递归&#xff0c;需要使用栈来实现。将左右下标分别push到栈中。在栈为…...

学生成绩管理系统(大一大作业)

功能 实现添加&#xff0c;排序&#xff0c;修改&#xff0c;保存等功能 库函数 #include<stdio.h> #include<stdlib.h> #include<windows.h> #include<string.h> 头文件 #define functioncreate(major) void major##compare(mana mn){\int i,j,s…...

数据结构:模拟栈

数据结构&#xff1a;模拟栈 题目描述参考代码 题目描述 输入样例 10 push 5 query push 6 pop query pop empty push 4 query empty输出样例 5 5 YES 4 NO参考代码 #include <iostream>using namespace std;const int N 1000010;int m, x; int q[N]; string op; int…...

02-2.3.6 顺序表和链表的比较

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏&#xff0c;今后还会不断更新。&#x1f9d1;‍&#x1f4bb; 此外&#xff0c;《程序员必备技能》专栏和《程序员必备工具》专栏&#xff08;该专栏暂未开设&#xff09;日后会逐步更新&#xff0c;感兴趣的小伙伴可以点一下订阅…...

C++ : 模板初阶

标题&#xff1a;C : 模板初阶 水墨不写bug 正文开始&#xff1a; C语言的问题 &#xff1a; 写不完的swap函数 在学习C语言时&#xff0c;我们有一个经常使用的函数swap函数&#xff0c;它可以将两个对象的值交换。 我们通常这样实现它&#xff1a; void swap(int t1,int t2)…...

FFA-Net:用于单图像去雾的特征融合注意力网络

摘要 论文链接&#xff1a;https://arxiv.org/pdf/1911.07559v2 在这篇论文中&#xff0c;我们提出了一种端到端的特征融合注意力网络&#xff08;FFA-Net&#xff09;来直接恢复无雾图像。FFA-Net架构由三个关键组件组成&#xff1a; 一种新颖的特征注意力&#xff08;FA&…...

网工内推 | 联通公司,云计算售前,AWS认证优先

01 联通数字科技有限公司 &#x1f537;招聘岗位&#xff1a;云计算售前工程师 &#x1f537;职责描述&#xff1a; 1.了解私有云&#xff0c;公有云&#xff0c;混合云等云计算技术知识&#xff0c;了解云计算行业现状及发展趋势。 2.承担区域项目售前工作支持&#xff0c;为…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...