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

代码随想录 动态规划Ⅸ

198. 打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

思路:状态转换机经典题目 dp[i][0]表示第i个房间不偷的最高金额,dp[i]表示第i个房屋偷的最高金额,状态转移方程为 dp[i][0] =max(dp[i-1][1] dp[i-1][0]), dp[i][1] = dp[i-1][0] + nums[i]. 最后返回max(dp[-1][0], dp[-1][1].初始化:dp[0][0] = 0, dp[0][0][1]=nums[0]

python:

二维dp

class Solution:def rob(self, nums: List[int]) -> int:dp= [[0,0] for _ in range(len(nums))]dp[0][0] = 0dp[0][1] = nums[0]for i in range(1, len(dp)):dp[i][0] = max(dp[i-1][1], dp[i-1][0])dp[i][1] = dp[i-1][0] + nums[i]return max(dp[-1][0], dp[-1][1])

一维dp:

class Solution:def rob(self, nums: List[int]) -> int:if len(nums) == 0:  return 0if len(nums) == 1:  return nums[0]dp = [0] * len(nums)dp[0] = nums[0]  # 将dp的第一个元素设置为第一个房屋的金额dp[1] = max(nums[0], nums[1])  # 将dp的第二个元素设置为第一二个房屋中的金额较大者# 遍历剩余的房屋for i in range(2, len(nums)):# 对于每个房屋,选择抢劫当前房屋和抢劫前一个房屋的最大金额dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])return dp[-1]  # 返回最后一个房屋中可抢劫的最大金额

 213. 打家劫舍 II

思路:与打家劫舍Ⅰ的区别在于这个成了一个环状,可以想办法把题目转换成打家劫舍Ⅰ。一个思路是分情况考虑,一个是考虑第一个房子,一个是考虑最后一个房子。然后从两种情况的最大值中选择最大的那个。

python:二维dp

class Solution:def rob(self, nums: List[int]) -> int:if len(nums) < 3:return max(nums)# 不抢劫第一个房屋result1 = self.robRange(nums[:-1])# 不抢劫最后一个房屋result2 = self.robRange(nums[1:])return max(result1, result2)# 打家劫舍Ⅰdef robRange(self, nums):dp = [[0, 0] for _ in range(len(nums))]dp[0][1] = nums[0]for i in range(1, len(nums)):dp[i][0] = max(dp[i - 1])dp[i][1] = dp[i - 1][0] + nums[i]return max(dp[-1])

python:双指针(一维dp)

class Solution:def rob(self, nums: List[int]) -> int:if not nums:  # 如果没有房屋,返回0return 0if len(nums) == 1:  # 如果只有一个房屋,返回该房屋的金额return nums[0]# 情况二:不抢劫第一个房屋prev_max = 0  # 上一个房屋的最大金额curr_max = 0  # 当前房屋的最大金额for num in nums[1:]:temp = curr_max  # 临时变量保存当前房屋的最大金额curr_max = max(prev_max + num, curr_max)  # 更新当前房屋的最大金额prev_max = temp  # 更新上一个房屋的最大金额result1 = curr_max# 情况三:不抢劫最后一个房屋prev_max = 0  # 上一个房屋的最大金额curr_max = 0  # 当前房屋的最大金额for num in nums[:-1]:temp = curr_max  # 临时变量保存当前房屋的最大金额curr_max = max(prev_max + num, curr_max)  # 更新当前房屋的最大金额prev_max = temp  # 更新上一个房屋的最大金额result2 = curr_maxreturn max(result1, result2)

337. 打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。

除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。

思路:递归加dp

因为是树,所以需要遍历。父亲结点是否可以考虑偷,考不考虑时的价值如何,需要根据左右孩子的状况而定,因此需要后序遍历,利用左右孩子的状态来决定父亲节点的状态,最后根据根节点的状态来得到最高金额。因为偷或不偷,那么设置每一个节点的dp数组为dp[0]dp[1], 转移方程为:dp[0] 的数值为左右孩子各自max(dp[0], dp[1])的最大值的和,dp[1]为左右孩子dp[0]的和加上节点的金额。

python:

class Solution:def rob(self, root: Optional[TreeNode]) -> int:final_dp = self.backtrack(root)return max(final_dp[0], final_dp[1])def backtrack(self, node):# stop conditionif not node:return [0,0]dp = [0,0]left_dp = self.backtrack(node.left)right_dp = self.backtrack(node.right)dp[0] = max(left_dp[0], left_dp[1]) + max(right_dp[0], right_dp[1])dp[1] = left_dp[0] + right_dp[0] + node.valreturn dp

相关文章:

代码随想录 动态规划Ⅸ

198. 打家劫舍 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金&#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统&#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入&#xff0c;系统会自动报警。 给定一个代表每个…...

【数据结构】散列表(哈希表)的学习知识总结

目录 1、散列表 2、散列函数 2.1 定义 2.2 散列函数的构造 2.2.1 除留余数法 2.2.2 直接定址法 2.2.3 数字分析法 2.2.4 平方取中法 3、冲突&#xff08;碰撞&#xff09; 4、处理冲突的方法 4.1 拉链法&#xff08;链接法&#xff09; 4.2 开放定址法 5、C语言…...

2023智慧云打印小程序源码多店铺开源版 +前端

智慧自助云打印系统/智慧云打印小程序源码 前端 这是一款全新的基于Thinkphp的最新自助打印系统&#xff0c;最新UI界面设计的云打印小程序源码...

利用亚马逊 云服务器 EC2 和S3免费套餐搭建私人网盘

网盘是一种在线存储服务&#xff0c;提供文件存储&#xff0c;访问&#xff0c;备份&#xff0c;贡献等功能&#xff0c;是我们日常中不可或缺的一种服务。很多互联网公司都为个人和企业提供免费的网盘服务。但这些免费服务都有一些限制&#xff0c;比如限制下载速度&#xff0…...

数据分析技能点-数据的种类

在日常生活中,数据无处不在。当你去超市购物时,你可能会注意到商品的价格、重量、口味等;当你在社交媒体上浏览时,你可能会注意到好友的点赞数、评论等。这些都是数据的一种形式,而了解这些数据的种类和特点有助于我们更好地理解和使用它们。 数据的基本分类 数据大致可…...

解读:ISO 14644-21:2023《洁净室及相关受控环境:悬浮粒子采样》发布指导粒子采样!

药品洁净实验室环境监测结果是否满足微生物检测需求&#xff0c;直接决定检测结果的有效性准确性&#xff0c;进行药品微生物检测&#xff0c;必须对实验环境进行日常和定期监测&#xff0c;其内容包括非生物活性的空气悬浮粒子数及有生物活性的微生物监测。 悬浮粒子监测是保证…...

Java --- MySQL8之索引优化与查询优化

目录 一、索引失效场景 1.1、全值匹配 1.2、最佳左前缀规则 1.3、主键插入顺序 1.4、计算、函数、类型转换(自动或手动)导致索引失效 1.5、类型转换导致索引失效 1.6、范围条件右边的列索引失效 1.7、不等于(! 或者<>)索引失效 1.8、is null可以使用索引&…...

澳大利亚新版《2023年消费品(36个月以下儿童玩具) 安全标准》发布 旨在降低危险小零件的伤害

2023年9月4日&#xff0c;澳大利亚政府发布了新的儿童玩具强制性安全标准《2023年消费品(36个月以下儿童玩具)安全标准》&#xff08;Consumer Goods (Toys for Children up to and including 36 Months of Age) Safety Standard 2023&#xff09;。该强制性标准旨在尽可能地降…...

表格内日期比较计算

需求&#xff1a;在表格中新增数据&#xff0c;计算开始日期中最早的和结束日期中最晚的&#xff0c;回显到下方。 <el-formref"formRef":model"ruleForm":rules"rules"style"margin-top: 20px;"label-position"top">…...

Linux内核启动流程-第二阶段start_kernel 函数

一. Linux内核启动 上一篇文章简单介绍了 Linux内核启动的第一阶段&#xff0c;即执行汇编流程。 本文简单了解一下&#xff0c;Linux内核启动的第二阶段&#xff1a;start_kernel函数&#xff0c;这是一个 C 函数。 本文续上一篇文章的学习&#xff0c;地址如下&#xff1a;…...

Disruptor:无锁队列设计的背后原理

简介 在高并发场景下&#xff0c;队列的速度和效率是关键。而Disruptor&#xff0c;一种高性能的并发队列&#xff0c;通过独特的设计&#xff0c;解决了传统队列在处理高并发时可能遇到的性能瓶颈。本文将深入分析Disruptor如何通过环形数组结构、元素位置定位以及无锁设计&a…...

网络编程-UDP协议(发送数据和接收数据)

需要了解TCP协议的&#xff0c;可以看往期文章 https://blog.csdn.net/weixin_43860634/article/details/133274701 TCP/IP参考模型 通过此图&#xff0c;可以了解UDP所在哪一层级中 代码案例 发送数据 package com.hidata.devops.paas.udp;import java.io.IOException; …...

AI绘画普及课【一】绘画入门

文章目录 一、AI 绘画入门1、Stable Diffusion VS. MidJourney2、Stable Diffusion 介绍3、Stable Diffusion 环境搭建4、文生图与图生图 一、AI 绘画入门 1、Stable Diffusion VS. MidJourney Midjourney 优点: 操作简单、出图绚丽多彩 缺点: 订阅付费充钱 内容有限制&a…...

Selenium和Requests搭配使用

Selenium和Requests搭配使用 前要1. CDP2. 通过requests控制浏览器2. 1 代码一2. 2 代码2 3. 通过selenium获取cookie, requests携带cookie请求 前要 之前有提过, 用selenium控制本地浏览器, 提高拟人化,但是效率比较低,今天说一种selenium和requests搭配使用的方法 注意: 一定…...

【JDK 8-函数式编程】4.4 Supplier

一、Supplier 接口 二、实战 Stage 1: 创建 Student 类 Stage 2: 创建方法 Stage 3: 调用方法 Stage 4: 执行结果 一、Supplier 接口 供给型 接口: 无入参&#xff0c;有返回值&#xff08;T : 出参类型&#xff09; 调用方法: T get(); 用途: 如 无参的工厂方法&#x…...

后端大厂面试-16道面试题

1 java集合类有哪些&#xff1f; List是有序的Collection&#xff0c;使用此接口能够精确的控制每个元素的插入位置&#xff0c;用户能根据索引访问List中元素。常用的实现List的类有LinkedList&#xff0c;ArrayList&#xff0c;Vector&#xff0c;Stack。 ArrayList是容量…...

产品经理认证(UCPM)备考心得

UCPM是联合国训练所CIFAL中心颁发的产品经理证书。如今&#xff0c;ESG是推动企业可持续发展的新潮流。UCPM作为一种可持续发展证书&#xff0c;为我们带来了一套先进科学、系统全面的产品管理模式&#xff0c;是产品管理领域公认的权威证书。那么&#xff0c;如何准备这张证书…...

E : A DS顺序表_删除有序表中的重复元素

Description 给定一个按升序排列的顺序表&#xff0c;请删除所有重复的元素&#xff0c;使得每个元素只出现一次&#xff0c;并输出处理后的顺序表。 Input 第一行输入t&#xff0c;表示有t个测试样例。 第二行起&#xff0c;每一行首先输入n&#xff0c;表示有n个元素&…...

前端教程-vite

官网 Vite中文网 视频教程 Vite世界指南&#xff08;带你从0到1深入学习 vite&#xff09;...

Java笔记三

包机制&#xff1a; 为了更好地组织类&#xff0c;Java提供了包机制&#xff0c;用于区别类名的命名空间。 包语句的语法格式为&#xff1a;pack pkg1[. pkg2[. pkg3...]]; 般利用公司域名倒置作为包名&#xff1b;如com.baidu.com&#xff0c;如图 导包&#xff1a; 为了能够…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...