当前位置: 首页 > 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; 为了能够…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

js 设置3秒后执行

如何在JavaScript中延迟3秒执行操作 在JavaScript中&#xff0c;要设置一个操作在指定延迟后&#xff08;例如3秒&#xff09;执行&#xff0c;可以使用 setTimeout 函数。setTimeout 是JavaScript的核心计时器方法&#xff0c;它接受两个参数&#xff1a; 要执行的函数&…...

精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑

精益数据分析&#xff08;98/126&#xff09;&#xff1a;电商转化率优化与网站性能的底层逻辑 在电子商务领域&#xff0c;转化率与网站性能是决定商业成败的核心指标。今天&#xff0c;我们将深入解析不同类型电商平台的转化率基准&#xff0c;探讨页面加载速度对用户行为的…...