当前位置: 首页 > 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; 创建抽象对象接…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...