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

代码随想录刷题第48天|LeetCode198打家劫舍、LeetCode213打家劫舍II、LeetCode337打家劫舍III

1、LeetCode198打家劫舍

题目链接:198、打家劫舍

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

2、递推公式:

如果偷第i房间,那么dp[i] = dp[i - 2] + nums[i] ;

如果不偷第i房间,那么dp[i] = dp[i - 1];

然后dp[i]取最大值,即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])。

3、初始化:

递推公式的基础就是dp[0] 和 dp[1]。

dp[0] = nums[0];

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

4、遍历顺序: 从前向后遍历;

5、举例推导。

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

2、LeetCode213打家劫舍II

题目链接:213、打家劫舍II

本题首尾连在一起,成环有三种情况:

考虑不包含首尾元素, 考虑包含首元素不包含尾元素, 考虑包含尾元素不包含首元素。

第二第三中情况包括第一种,所以只需考虑去掉首元素,去掉尾元素,这两种情况下,哪种的dp[i]更大。

递归五部曲与上题一样,由于要去掉首尾元素,定义一个start、end区间

robRange(vector<int>& nums, int start, int end)。

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

3、LeetCode337打家劫舍III

题目链接:337、打家劫舍III

第一次做树形dp,有点难理解。

1、dp数组(dp table)以及下标的含义:下标为0记录不偷该节点所得到的的最大金钱,下标为1记录偷该节点所得到的的最大金钱。

2、递归树时的终止条件:

如果遇到空节点的话,无论偷还是不偷都是0。

if (cur == NULL)  return vector<int>{0,0};    注意这里是花括号。

3、遍历顺序:

后序遍历。

递归左节点,得到左节点偷与不偷的金钱。

递归右节点,得到右节点偷与不偷的金钱。

4、递推公式:

偷该节点,则左右孩子不能偷,int val1 = cur->val + left[0] + left[1];

不偷该节点,则左右孩子要偷,每个孩子里偷一个最大的,int val2 = max(left[0],left[1]) + max(right[0], right[1]);

最后当前节点的状态就是{val2, val1}; 即:{不偷当前节点得到的最大金钱,偷当前节点得到的最大金钱}。

5、举例推导:

 

class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}vector<int> robTree(TreeNode* cur){if (cur == NULL) return vector<int>{0,0};vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);int val1 = cur->val + left[0] + right[0];int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2,val1};}
};

相关文章:

代码随想录刷题第48天|LeetCode198打家劫舍、LeetCode213打家劫舍II、LeetCode337打家劫舍III

1、LeetCode198打家劫舍 题目链接&#xff1a;198、打家劫舍 1、dp[i]&#xff1a;考虑下标i&#xff08;包括i&#xff09;以内的房屋&#xff0c;最多可以偷窃的金额为dp[i]。 2、递推公式&#xff1a; 如果偷第i房间&#xff0c;那么dp[i] dp[i - 2] nums[i] &#xf…...

C# NTS 获取MuliiLineString中的所有线

/// <summary>/// 获取多段线的所有线/// </summary>/// <param name"ml"></param>/// <returns></returns>public static List<LineString> GetLineStrings(this MultiLineString ml){List<LineString> lineString…...

CodeWhisperer插件使用体验

官方教程点击跳转 使用工具 1.vscode 2.插件(AWS Toolkit),免费使用 安装以后如何使用 1.首先要有一个aws账号 2.插件下载好以后登录aws账号&#xff0c;我们主要用这款插件的CodeWhisperer这个功能&#xff0c;其它的自行看官方教程了解。 注意事项&#xff1a;我们在从vs…...

机器学习笔记 - 多实例学习(MIL)弱监督学习

一、多实例学习概述 多实例学习(MIL)是一种弱监督学习形式,其中训练实例被排列在称为袋的集合中,并为整个袋提供标签。这种方式越来越受到人们的关注,因为它自然适合各种问题,并允许利用弱标记数据。因此,它被应用于计算机视觉和文档分类等不同的应用领域。 多实例学习(…...

SQL Server 2008 定时自动备份和自动删除方法

SQL Server 2008 数据定时自动备份和自动删除方法&#xff0c;同一个计划兼备数据备份数数据删除的操作方法 工具/原料 SQL Server 2008 方法/步骤 1、 点击实例名下的【管理】-【维护计划】-点击鼠标右键&#xff0c;点击【维护计划向导】&#xff0c;填写计划名称&…...

代码生成器实现

代码生成器实现 实现封装元数据的工具类实现代码生成器的代码编写掌握模板创建的 构造数据模型 需求分析 借助Freemarker机制可以方便的根据模板生成文件&#xff0c;同时也是组成代码生成器的核心部分。对于Freemarker而 言&#xff0c;其强调 数据模型 模板 文件 的思…...

【Python基础】Python函数(基本函数)

文章目录 Python函数1、函数多返回值2、函数多种传参方式(1)位置参数(2)关键字参数(3)缺省参数(4)不定长参数位置传递关键字传递 3、小结 Python函数 1、函数多返回值 Q&#xff1a;如果一个函数要有多个返回值&#xff0c;该如何书写代码&#xff1f; # 使用多个变量&#…...

Vue3 + TS + Vite —— 大屏可视化 项目实战

前期回顾 Vue3 Ts Vite pnpm 项目中集成 —— eslint 、prettier、stylelint、husky、commitizen_彩色之外的博客-CSDN博客搭建VIte Ts Vue3项目并集成eslint 、prettier、stylelint、huskyhttps://blog.csdn.net/m0_57904695/article/details/129950163?spm1001.2014…...

EasyExcel 批量导入并校验数据

文章目录 前言一、pom二、使用步骤1.导入对象2.读入数据并保存 前言 EasyExcel 批量导入并校验数据 一、pom <dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><version>2.2.7</version></depend…...

亚马逊、Allegro卖家建立属于自己的测评系统,实现批量优质账号养成

卖家搭建一套完整的测评系统&#xff0c;卖家自己能够养出批量优质账号&#xff0c;并完全掌控真实买家的浏览、加购、下单和评价等风控数据规律。我们的系统能够自主加速推广&#xff0c;防御反击&#xff0c;同时节省运营成本&#xff0c;实现高效的测评运营。 我们的系统支…...

springboot的目录结构作用

springboot单体项目结构大概如下。 代码都在src/main下&#xff0c; java是后端代码 java下最基本的包 dao(mapper) entity(model) service controller 其他的包根据项目需求扩展。 resources下是配置文件。 如果不是前后端分离&#xff0c;resources下放的是静态文件…...

微信小程序基础使用-请求数据并渲染

小程序基本使用-请求数据并渲染 小程序模板语法-数据绑定 在js中定义数据 Page({data: {isOpen: true,message: hello world!} })小程序的data是一个对象&#xff0c;不同于vue的data是一个函数 在模块中获取使用数据 小程序中使用 {{}} 实现数据与模板的绑定 内容绑定&a…...

代码随想录训练营Day55| 392.判断子序列 ;115.不同的子序列

392.判断子序列 class Solution {public boolean isSubsequence(String s, String t) {int m s.length();int n t.length();if(m>n) return false;int[][] dp new int[m1][n1];dp[0][0]0;for(int i1;i<m;i){for(int j1;j<n;j){if(s.charAt(i-1)t.charAt(j-1)){dp[i…...

网络作业9【计算机网络】

网络作业9【计算机网络】 前言推荐网络作业9一. 单选题&#xff08;共12题&#xff0c;36分&#xff09;二. 多选题&#xff08;共1题&#xff0c;3分&#xff09;三. 填空题&#xff08;共2题&#xff0c;10分&#xff09;四. 阅读理解&#xff08;共1题&#xff0c;17分&…...

C++ QT 上传图片至mysql数据库

以下是一个简单的C QT上传图片至MySQL数据库的代码示例&#xff1a; #include <QtSql> #include <QFile> #include <QByteArray> int main() { //连接数据库 QSqlDatabase db QSqlDatabase::addDatabase("QMYSQL"); …...

2023去水印小程序saas系统源码修复独立版v1.0.3+uniapp前端

&#x1f388; 限时活动领体验会员&#xff1a;可下载程序网创项目短视频素材 &#x1f388; &#x1f389; 有需要的朋友记得关赞评&#xff0c;阅读文章底部来交流&#xff01;&#xff01;&#xff01; &#x1f389; ✨ 源码介绍 一个基于uniapp写的小程序&#xff0c;后端…...

【ChatGPT】数据科学 ChatGPT Cheat Sheet 书籍分享(阿里云盘下载)

封皮 以下为书中部分内容的机器翻译 我们的重要提示指南 1. 以 AI 角色的描述开始提示。 例如&#xff0c;“你是{x}”或“我希望你扮演{x}”。如果您不确定&#xff0c;请尝试“你是一个有帮助的助手”。 例如&#xff0c;您是 OpenAI 的数据科学家&#xff0c;您正在研究大型…...

使用 Docker-compose 搭建lnmp

服务编排&#xff1a; 应用编排&#xff1a; 单机环境下&#xff1a;shell/python脚本多机/集群环境下&#xff1a;ansible、saltstack、pubbet docker容器编排&#xff1a; 单机&#xff1a;docker-compose多机/集群&#xff1a;docker swarm&#xff0c;mesos marathon&a…...

chatgpt赋能python:Python中的矩阵合并方法:介绍和使用方法

Python中的矩阵合并方法: 介绍和使用方法 矩阵合并是Python编程中常用的操作之一&#xff0c;特别是针对数据分析、机器学习和深度学习等领域。Python提供了多种方法来合并矩阵&#xff0c;本文将介绍这些方法并分享如何在实际应用中使用它们。 普通矩阵合并 最基础的矩阵合…...

Java动态代理:优化静态代理模式的灵活解决方案

文章目录 代理模式定义具体实现分析优缺点 优化使用动态代理解决优化相关知识动态代理种类场景应用 代理模式 定义 代理模式&#xff0c;为其他对象提供一种代理以控制对这个对象的访问 具体实现 代理模式的具体实现描述可以分为以下几个步骤&#xff1a; 创建抽象对象接…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

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

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

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...