动态规划 —— dp 问题-打家劫舍II
1.打家劫舍II
题目链接:
213. 打家劫舍 II - 力扣(LeetCode)
https://leetcode.cn/problems/house-robber-ii/
2. 题目解析
通过分类讨论,将环形问题转换为两个线性的“打家劫舍|”
当偷第一个位置的时候,rob1在(2,n-2)的区间进行一次打家劫舍|,当不偷第一个位置的时候,rob1在(1,n-1)的区间进行一次打家劫舍|
3. 算法原理
状态表示:以某一个位置为结尾或者以某一个位置为起点
dp[i]表示:偷到i位置的时候,此时的最大金额分两种情况:
1.f[i]表示:偷到i位置的时候,当前位置nums[i]必偷,此时的最大金额
2.g[i]表示:偷到i位置的时候,当前位置nums[i]不偷,此时的最大金额
2. 状态转移方程
根据最近的一步来划分问题:
到达dp[i][j]有两种情况:
1. f[i]=g[i-1] + nums[i]
2. g[i]:a. 当选择i-1的位置时:f[i-1]
b.当不选择i-1的位置时:g[i-1]
g[i]=max(f[i-1],g[i-1])
3. 初始化 :把dp表填满不越界,让后面的填表可以顺利进行
本题初始化为:f[0]=nums[0] g[0]=0
4. 填表顺序
本题的填表顺序是:从左往右,两个表一起填
5. 返回值 :题目要求 + 状态表示
偷到最后一个位置分为两种情况:偷和不偷
本题的返回值是:max(f[n-1],g[n-1])
4.代码
动态规划的固定四步骤:1. 创建一个dp表
2. 在填表之前初始化
3. 填表(填表方法:状态转移方程)
4. 确定返回值
class Solution {
public:int rob(vector<int>& nums) {int n=nums.size();return max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));}int rob1(vector<int>& nums,int left,int right)//左边界和右边界{//处理一下边界情况if(left>right) return 0;//如果l>r,那么说明区间不存在int n=nums.size();vector<int>f(n);//开辟两个dp表auto g=f;//将l到r这段区间的值初始化f[left]=nums[left];//从l+1的位置开始填表for(int i=left+1;i<=right;i++){f[i]=g[i-1]+nums[i];g[i]=max(f[i-1],g[i-1]);}return max(f[right],g[right]);}
};
完结撒花~
相关文章:
动态规划 —— dp 问题-打家劫舍II
1.打家劫舍II 题目链接: 213. 打家劫舍 II - 力扣(LeetCode)https://leetcode.cn/problems/house-robber-ii/ 2. 题目解析 通过分类讨论,将环形问题转换为两个线性的“打家劫舍|” 当偷第一个位置的时候,rob1在&#…...
Java基础-组件及事件处理(上)
(创作不易,感谢有你,你的支持,就是我前行的最大动力,如果看完对你有帮助,请留下您的足迹) 目录 Swing 概述 MVC 架构 Swing 特点 控件 SWING UI 元素 JFrame SWING 容器 说明 常用方法 示例&a…...
Python实例:爱心代码
前言 在编程的奇妙世界里,代码不仅仅是冰冷的指令集合,它还可以成为表达情感、传递温暖的独特方式。今天,我们将一同探索用 Python 语言绘制爱心的神奇之旅。 爱心,这个象征着爱与温暖的符号,一直以来都在人类的情感世界中占据着特殊的地位。而通过 Python 的强大功能,…...
图解大模型训练系列:序列并行3,Ring Attention
在序列并行系列中,我们将详细介绍下面四种常用的框架/方法: Megatron Sequence Parallelism:本质是想通过降低单卡激活值大小的方式,尽可能多保存激活值,少做重计算,以此提升整体训练速度,一般…...
pyspark基础准备
1.前言介绍 学习目标:了解什么是Speak、PySpark,了解为什么学习PySpark,了解课程是如何和大数据开发方向进行衔接 使用pyspark库所写出来的代码,既可以在电脑上简单运行,进行数据分析处理,又可以把代码无缝…...
Netty报错
问题:因客户反馈Netty版本低,影响性能,建议提升。于是,我将所有Netty版本从4.1.82.Final到4.1.114.Final后,报下面的错误,java.lang.NoClassDefFoundError: io/netty/util/Recycler$EnhancedHandle…...
Kafka 之顺序消息
前言: 在分布式消息系统中,消息的顺序性是一个重要的问题,也是一个常见的业务场景,那 Kafka 作为一个高性能的分布式消息中间件,又是如何实现顺序消息的呢?本篇我们将对 Kafka 的顺序消息展开讨论。 Kafk…...
Kafka 之批量消息发送消费
前言: 前面我们分享了 Kafka 的一些基础知识,以及 Spring Boot 集成 Kafka 完成消息发送消费,本篇我们来分享一下 Kafka 的批量消息发送消费。 Kafka 系列文章传送门 Kafka 简介及核心概念讲解 Spring Boot 整合 Kafka 详解 Kafka Kafka…...
【大数据学习 | kafka】kafka的偏移量管理
1. 偏移量的概念 消费者在消费数据的时候需要将消费的记录存储到一个位置,防止因为消费者程序宕机而引起断点消费数据丢失问题,下一次可以按照相应的位置从kafka中找寻数据,这个消费位置记录称之为偏移量offset。 kafka0.9以前版本将偏移量信…...
实景三维赋能森林防灭火指挥调度智慧化
森林防灭火工作是保护森林资源和生态环境的重要任务。随着信息技术的发展,实景三维技术在森林防灭火指挥调度中的应用日益广泛,为提升防灭火工作的效率和效果提供了有力支持。 一、森林防灭火面临的挑战 森林火灾具有突发性强、破坏性大、蔓延速度快、…...
【C++课程学习】:string的模拟实现
🎁个人主页:我们的五年 🔍系列专栏:C课程学习 🎉欢迎大家点赞👍评论📝收藏⭐文章 目录 一.string的主体框架: 二.string的分析: 🍔构造函数和析构函数&a…...
Linux(VMware + CentOS )设置固定ip
需求:设置ip为 192.168.88.130 先关闭虚拟机 启动虚拟机 查看当前自动获取的ip 使用 FinalShell 通过 ssh 服务远程登录系统,更换到 root 用户 修改ip配置文件 vim /etc/sysconfig/network-scripts/ifcfg-ens33 重启网卡 systemctl restart network …...
安卓 android studio各版本下载地址(官方)
https://developer.android.google.cn/studio/archive 别用中文,右上角的语言切换成英文...
如何在一个 Docker 容器中运行多个进程 ?
在容器化的世界里,Docker 彻底改变了开发人员构建、发布和运行应用程序的方式。Docker 容器封装了运行应用程序所需的所有依赖项,使其易于跨不同环境一致地部署。然而,在单个 Docker 容器中管理多个进程可能具有挑战性,这就是 Sup…...
poetry 配置多个cuda环境心得
操作系统:ubuntu22.04 LTS python版本:3.12.7 最近学习了用poetry配置python虚拟环境,当为不同的项目配置cuda时,会遇到不同的项目使用的cuda版本不一致的情况。 像torch 这样的库,它们会对cuda-toolkit有依赖&…...
网络编程入门
目录 1.网络编程入门 1.1 网络编程概述【理解】 1.2 网络编程三要素【理解】 1.3 IP地址【理解】 1.4InetAddress【应用】 1.5端口和协议【理解】 2.UDP通信程序 2.1 UDP发送数据【应用】 2.2UDP接收数据【应用】 2.3UDP通信程序练习【应用】 3.TCP通信程序 3.1TCP…...
Linux-socket详解
Linux-socket详解_socket linux-CSDN博客...
SQL Server 2022安装要求(硬件、软件、操作系统等)
SQL Server 2022安装要求 1、硬件要求2、软件要求3、操作系统支持4、Server Core 支持5、跨语言支持6、磁盘空间要求 1、硬件要求 以下内存和处理器要求适用于所有版本的 SQL Server: 组件要求存储SQL Server 要求最少 6 GB 的可用硬盘驱动器空间。 磁盘空间要求随…...
“众店模式”:创新驱动下的商业新生态
在数字化浪潮的推动下,传统商业模式正经历着前所未有的转型。“众店模式”作为一种新兴的商业模式,以其独特的商业逻辑和创新的玩法,为商家和消费者构建了一个共赢的商业新生态。 一、“众店模式”的核心构成 “众店模式”的成功࿰…...
54. 螺旋矩阵
https://leetcode.cn/problems/spiral-matrix/description/?envTypestudy-plan-v2&envIdtop-100-liked观察示例中的输出轨迹我们可以想到如下设计: 1.在朝某一方向行进到头后的改变方向是确定的,左->下,下->右,右->…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...
