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

第三十九天打卡,今天解决打家劫舍系列问题,树形dp比较难。


198.打家劫舍

题目链接

解题过程

  • dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]

在这里插入图片描述

  • 要么不偷这一间,那就是前面那间赚的多;要么偷这一间,加上前前一间最多偷的金额。

动态规划

class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        if (len == 2) return max(nums[0], nums[1]);
        vector<int>dp(nums.size());
        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.back();
    }
};

213.打家劫舍Ⅱ

题目链接

解题过程

  • 与打家劫舍Ⅰ的区别就是,这里第一个元素和最后一个元素不能同时选择,所以分两种情况就可以做

动态规划

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        if (nums.size() == 2) return max(nums[0], nums[1]);
        int rob1 = getRob(nums, 0, nums.size() - 2);
        int rob2 = getRob(nums, 1, nums.size() - 1);
        return max(rob1, rob2);
    }
    int getRob(vector<int>& nums, int start, int end) {
        if (end == start) return nums[start];
        vector<int>dp(nums.size());
        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 - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
};

337.打家劫舍Ⅲ

题目链接

解题过程

  • 没想到这题怎么做,用树形dp,每个节点记录偷或者不偷该点能偷得的总共最大钱数。用后序遍历,因为要用到子节点的结果

在这里插入图片描述

树形dp

class Solution {
private:
    vector<int> backtracking(TreeNode* node) {
        if (node == nullptr) return { 0,0 }; 
        vector<int> left = backtracking(node->left);
        vector<int> right = backtracking(node->right);
        int val1 = max(left[0], left[1]) + max(right[0], right[1]); // 不偷该节点,可以偷或不偷左右节点
        int val2 = left[0] + right[0] + node->val; // 偷该节点,则不能偷子节点
        return { val1,val2 };
    }
    
public:
    int rob(TreeNode* root) {
        vector<int>result = backtracking(root);
        return max(result[0], result[1]);
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/882803.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SQL面试常见题目

SQL面试常见题目涉及多个方面&#xff0c;包括数据查询、数据操作、表的设计与优化等。以下列举一些经典的SQL面试题目&#xff0c;并附上解析答案&#xff1a; 1. 查询一张表中重复的数据 题目&#xff1a; 给定一个表 employees&#xff0c;包含 id, name, salary 列。如何…

Uniapp时间戳转时间显示/时间格式

使用uview2 time 时间格式 | uView 2.0 - 全面兼容 nvue 的 uni-app 生态框架 - uni-app UI 框架 <text class"cell-tit clamp1">{{item.create_time}} --- {{ $u.timeFormat(item.create_time, yyyy-mm-dd hh:MM:ss)}} </text>

【Java 问题】基础——基础语法

基础语法 7. Java 有哪些数据类型8.自动类型转换、强制类型转换&#xff1f;9.什么是自动拆箱/封箱&#xff1f;10.&和&&有什么区别&#xff1f;11.switch 是否能作用在 byte/long/String上&#xff1f;12.break ,continue ,return 的区别及作用&#xff1f;13.用最…

Java ----常用类

包装类 包装类的分类 1) 针对八种基本数据类型相应的引用类型—包装类2) 有了类的特点&#xff0c;就可以调用类中的方法。3) 如图 包装类和基本数据的转换 jdk5 前的手动装箱和拆箱方式&#xff0c;装箱&#xff1a;基本类型转包装类型&#xff0c;拆箱&#xff1a;包装类型…

Flutter 安装,配置,运行第一个app 1

起因&#xff0c; 目的: flutter, 其实几年前&#xff0c;我就写过。 当时纯属是个人兴趣&#xff0c;随意探索。 当时我也写了几篇笔记: 比如这一篇还有这个 flutter&#xff0c;其实不难&#xff0c;比较繁琐&#xff0c;小的知识点很多. flutter&#xff0c; 又是环境配…

树与图的深度优先遍历(dfs的图论中的应用)

模板题 846. 树的重心 给定一颗树&#xff0c;树中包含 n 个结点&#xff08;编号 1∼n&#xff09;和 n−1条无向边。 请你找到树的重心&#xff0c;并输出将重心删除后&#xff0c;剩余各个连通块中点数的最大值。 重心定义&#xff1a;重心是指树中的一个结点&#xff0…

7天速成前端 ------学习日志 (继苍穹外卖之后)

前端速成计划总结&#xff1a; 全26h课程&#xff0c;包含html&#xff0c;css&#xff0c;js&#xff0c;vue3&#xff0c;预计7天内学完。 起始日期&#xff1a;9.16 预计截止&#xff1a;9.22 每日更新&#xff0c;学完为止。 学前计划 课…

《粮油与饲料科技》是什么级别的期刊?是正规期刊吗?能评职称吗?

问题解答 问&#xff1a;《粮油与饲料科技》是不是核心期刊&#xff1f; 答&#xff1a;不是&#xff0c;是知网收录的第一批认定 学术期刊。 问&#xff1a;《粮油与饲料科技》级别&#xff1f; 答&#xff1a;省级。主管单位&#xff1a;中文天地出版传媒集团股份有限公司…

漏洞复现_永恒之蓝

1.概述 永恒之蓝&#xff08;EternalBlue&#xff09;是一个影响Windows操作系统的远程代码执行漏洞&#xff0c;编号为CVE-2017-0144&#xff0c;最初由美国国家安全局&#xff08;NSA&#xff09;开发并利用&#xff0c;后来被黑客组织Shadow Brokers泄露。该漏洞存在于SMBv…

Gitee Pipeline 从入门到实战【详细步骤】

文章目录 Gitee Pipeline 简介Gitee Pipeline 实战案例 1 - 前端部署输入源NPM 构建Docker 镜像构建Shell 命令执行案例 2 - 后端部署全局参数输入源Maven 构建Docker 镜像构建Shell 命令执行参考🚀 本文目标:快速了解 Gitee Pipeline,并实现前端及后端打包部署。 Gitee Pi…

【d46】【Java】【力扣】876.链表的中间结点

思路 先获得总体长度&#xff0c; 再得到中间节点 的索引&#xff0c;&#xff0c;这里的索引是从1开始的索引&#xff0c;而不是从0开始的索引(这种理解方式更简单) 排错&#xff1a;另一个思路&#xff1a;将链表都放进list&#xff0c;获得中间的数字&#xff0c;然后遍历…

AfuseKt1.3.6-10110功能强大的安卓网络视频播放器,支持多种在线存储和媒体管理平台!

AfuseKt 是一款功能强大的安卓网络视频播放器&#xff0c;专为满足用户对多样化媒体播放需求而设计。它不仅支持多种流行的在线存储和媒体管理平台&#xff0c;如阿里云盘、Alist、WebDAV和Emby等&#xff0c;还提供了刮削功能和海报墙展示&#xff0c;使得用户能够更加便捷地管…

船舶检测系统源码分享

船舶检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Vision …

深度学习|误差逆传播:梯度速解

文章目录 引言链式法则误差逆传播加法的逆传播乘法的逆传播逆传播求梯度 SoftmaxWithLoss 层正向传播逆传播代码实现参考 结语 引言 我们知道训练神经网络模型的核心是以损失函数为基准来调整优化网络参数&#xff0c;使得网络的输出尽可能接近真实标签。在神经网络中&#xf…

网络原理(4)——网络层(IP)、数据链路层

1. IP 协议 基本概念&#xff1a; 主机&#xff1a;配有 IP 地址&#xff0c;但是不进行路由控制的设备 路由器&#xff1a;即配有 IP 地址&#xff0c;又能进行路由控制 节点&#xff1a;主机和路由器的统称 IP 协议报头格式 1) 4 位版本&#xff1a;实际上只有两个取值&…

RabbitMQ 高级特性——发送方确认

文章目录 前言发送方确认confirm 确认模式return 退回模式 常见面试题 前言 前面我们学习了 RabbitMQ 中交换机、队列和消息的持久化&#xff0c;这样能够保证存储在 RabbitMQ Broker 中的交换机和队列中的消息实现持久化&#xff0c;就算 RabbitMQ 服务发生了重启或者是宕机&…

安卓13去掉下拉菜单的Dump SysUI 堆的选项 android13删除Dump SysUI 堆

总纲 android13 rom 开发总纲说明 文章目录 1.前言2.问题分析3.代码分析3.1 位置13.2 位置24.代码修改5.编译6.彩蛋1.前言 客户需要去掉下拉菜单里面的Dump SysUI 堆图标,不让使用这个功能。 2.问题分析 android的下拉菜单在systemui里面,这里我们只需要定位到对应的添加代…

通义灵码AI 程序员正式发布:写代码谁还动手啊

虽然见不到面 但你已深潜我心 前几天&#xff0c;在 2024 年的杭州云栖大会上&#xff0c;随着通义大模型能力的全面提升&#xff0c;阿里云通义灵码这位中国的首位 AI 程序员也迎来重大的升级。 一年前这位 AI 程序员还只能完成基础的编程任务&#xff0c;到现在可以做到几…

2024年华为杯研究生数学建模竞赛D题(时空演化模型+脆性指数 完整文章|可视化)

2024年华为杯研究生数学建模竞赛D题 全文请从 底部名片 处加群获取哦~ 问题重述 题目背景&#xff1a; 地理系统是由自然和人文多要素综合作用形成的复杂巨系统。传统上&#xff0c;地理学家通过宏观结构和定性分析方法描述地理系统的主导特征&#xff0c;如地形分布、气候…

LabVIEW闪退

LabVIEW闪退或无法启动可能由多个原因引起&#xff0c;特别是在使用了一段时间后突然发生的问题。重启电脑后 LabVIEW 和所有 NI 软件都无法打开&#xff0c;甚至在卸载和重装时也没有反应。这种情况通常与系统环境、软件冲突或 NI 软件组件的损坏有关。 1. 检查系统和软件冲突…