代码随想录算法训练营第五十天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III
代码随想录算法训练营第五十天
198.打家劫舍
题目链接:198.打家劫舍
- 确定dp数组以及下标的含义:dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。
- 确定递推公式:max(dp[i - 1], dp[i - 2] + nums[i]);,不偷当前节点和偷当前节点哪个获利最大就取哪个
- dp数组如何初始化:dp[0]=nums[0],只有一个必须偷。dp[1]=max(nums[0],nums[1])一共2个元素,只能偷一个最大的
- 确定遍历顺序:从前向后遍历。
- 打印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.打家劫舍 题目链接:198.打家劫舍 确定dp数组以及下标的含义:dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。确定递推公式:max(dp[i - 1],…...
VB.net 进行CAD二次开发(二)
利用参考文献2,添加面板 执行treeControl New UCTreeView()时报一个错误: 用户代码未处理 System.ArgumentException HResult-2147024809 Message控件不支持透明的背景色。 SourceSystem.Windows.Forms StackTrace: 在 System.Windows…...
安徽某高校数据挖掘作业6
1 根据附件中year文件,编辑Python程序绘制年销售总额分布条形图和年净利润分布条形图,附Python程序和图像。 2 根据附件中quarter和quarter_b文件,编辑Python程序绘制2018—2020年销售额和净利润折线图,附Python程序和图像。 3 …...
CMakeLists.txt和Package.xml
CMakeLists.txt和Package.xml CMakeLists.txt 总览 CMakeLists.txt 是用于定义如何构建 ROS (Robot Operating System) 包的 CMake 脚本文件。CMake 是一个跨平台的构建系统,用于自动化编译过程。在 ROS 中,CMakeLists.txt 文件指定了如何编译代码和链…...
Debian常用命令详解
Debian常用命令详解 Debian是一个流行的Linux发行版,它以其稳定性、强大的包管理系统和丰富的软件仓库而著称。对于Debian用户来说,掌握一些常用的命令行工具和命令是日常系统管理和维护的基础。下面,我们将介绍一些Debian系统中常用的命令。…...
代码随想录算法训练营day29|491.递增子序列、46.全排列、47.全排列II
递增子序列 491. 非递减子序列 - 力扣(LeetCode) 非递减子序列,则答案的子集中,需保持下一个元素大于等于前一个元素的顺序,由于题目中指出,所有的子序列长度需大于等于2,考虑当条件为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)
上几章讲了几种策略,策略10,11,30,40。 SAP PP学习笔记14 - MTS(Make-to-Stock) 按库存生产(策略10),以及生产计划的概要-CSDN博客 SAP PP学习笔记15 - MTS(Make-to-St…...
网页音频提取在线工具有哪些 网页音频提取在线工具下载
别再到处去借会员账号啦。教你一招,无视版权和地区限制,直接下载网页中的音频文件。没有复杂的操作步骤,也不用学习任何代码。只要是网页中播放的音频文件,都可以把它下载到本地保存。 一、网页音频提取在线工具有哪些 市面上的…...
【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显示为:select * from ‘tableName’ 2、解决方法 mapper文件种使用${tableName}而不是#{tableName}...
C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍
文章目录 前言一、快速排序非递归二、归并排序五、归并排序非递归总结 前言 C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍 一、快速排序非递归 快速排序非递归的定义 快速排序非递归,需要使用栈来实现。将左右下标分别push到栈中。在栈为…...
学生成绩管理系统(大一大作业)
功能 实现添加,排序,修改,保存等功能 库函数 #include<stdio.h> #include<stdlib.h> #include<windows.h> #include<string.h> 头文件 #define functioncreate(major) void major##compare(mana mn){\int i,j,s…...
数据结构:模拟栈
数据结构:模拟栈 题目描述参考代码 题目描述 输入样例 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 顺序表和链表的比较
喜欢《数据结构》部分笔记的小伙伴可以订阅专栏,今后还会不断更新。🧑💻 此外,《程序员必备技能》专栏和《程序员必备工具》专栏(该专栏暂未开设)日后会逐步更新,感兴趣的小伙伴可以点一下订阅…...
C++ : 模板初阶
标题:C : 模板初阶 水墨不写bug 正文开始: C语言的问题 : 写不完的swap函数 在学习C语言时,我们有一个经常使用的函数swap函数,它可以将两个对象的值交换。 我们通常这样实现它: void swap(int t1,int t2)…...
FFA-Net:用于单图像去雾的特征融合注意力网络
摘要 论文链接:https://arxiv.org/pdf/1911.07559v2 在这篇论文中,我们提出了一种端到端的特征融合注意力网络(FFA-Net)来直接恢复无雾图像。FFA-Net架构由三个关键组件组成: 一种新颖的特征注意力(FA&…...
网工内推 | 联通公司,云计算售前,AWS认证优先
01 联通数字科技有限公司 🔷招聘岗位:云计算售前工程师 🔷职责描述: 1.了解私有云,公有云,混合云等云计算技术知识,了解云计算行业现状及发展趋势。 2.承担区域项目售前工作支持,为…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...
免费批量Markdown转Word工具
免费批量Markdown转Word工具 一款简单易用的批量Markdown文档转换工具,支持将多个Markdown文件一键转换为Word文档。完全免费,无需安装,解压即用! 官方网站 访问官方展示页面了解更多信息:http://mutou888.com/pro…...
React、Git、计网、发展趋势等内容——前端面试宝典(字节、小红书和美团)
React React Hook实现架构、.Hook不能在循环嵌套语句中使用 , 为什么,Fiber架构,面试向面试官介绍,详细解释 用户: React Hook实现架构、.Hook不能在循环嵌套语句中使用 , 为什么,Fiber架构,面试向面试官介绍&#x…...
SDU棋界精灵——硬件程序ESP32实现opus编码
一、 音频处理框架 该项目基于Espressif的音频处理框架构建,核心组件包括 ESP-ADF 和 ESP-SR,以下是完整的音频处理框架实现细节: 1.核心组件 (1) 音频前端处理 (AFE - Audio Front-End) main/components/audio_pipeline/afe_processor.c功能: 声学回声…...
Redis:常用数据结构 单线程模型
🌈 个人主页:Zfox_ 🔥 系列专栏:Redis 🔥 常用数据结构 🐳 Redis 当中常用的数据结构如下所示: Redis 在底层实现上述数据结构的过程中,会在源码的角度上对于上述的内容进行特定的…...
