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

动态规划 —— dp 问题-打家劫舍II

1.打家劫舍II

题目链接:

213. 打家劫舍 II - 力扣(LeetCode)icon-default.png?t=O83Ahttps://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 题目链接&#xff1a; 213. 打家劫舍 II - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/house-robber-ii/ 2. 题目解析 通过分类讨论&#xff0c;将环形问题转换为两个线性的“打家劫舍|” 当偷第一个位置的时候&#xff0c;rob1在&#…...

Java基础-组件及事件处理(上)

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 Swing 概述 MVC 架构 Swing 特点 控件 SWING UI 元素 JFrame SWING 容器 说明 常用方法 示例&a…...

Python实例:爱心代码

前言 在编程的奇妙世界里,代码不仅仅是冰冷的指令集合,它还可以成为表达情感、传递温暖的独特方式。今天,我们将一同探索用 Python 语言绘制爱心的神奇之旅。 爱心,这个象征着爱与温暖的符号,一直以来都在人类的情感世界中占据着特殊的地位。而通过 Python 的强大功能,…...

图解大模型训练系列:序列并行3,Ring Attention

在序列并行系列中&#xff0c;我们将详细介绍下面四种常用的框架/方法&#xff1a; Megatron Sequence Parallelism&#xff1a;本质是想通过降低单卡激活值大小的方式&#xff0c;尽可能多保存激活值&#xff0c;少做重计算&#xff0c;以此提升整体训练速度&#xff0c;一般…...

pyspark基础准备

1.前言介绍 学习目标&#xff1a;了解什么是Speak、PySpark&#xff0c;了解为什么学习PySpark&#xff0c;了解课程是如何和大数据开发方向进行衔接 使用pyspark库所写出来的代码&#xff0c;既可以在电脑上简单运行&#xff0c;进行数据分析处理&#xff0c;又可以把代码无缝…...

Netty报错

问题&#xff1a;因客户反馈Netty版本低&#xff0c;影响性能&#xff0c;建议提升。于是&#xff0c;我将所有Netty版本从4.1.82.Final到4.1.114.Final后&#xff0c;报下面的错误&#xff0c;java.lang.NoClassDefFoundError: io/netty/util/Recycler$EnhancedHandle&#xf…...

Kafka 之顺序消息

前言&#xff1a; 在分布式消息系统中&#xff0c;消息的顺序性是一个重要的问题&#xff0c;也是一个常见的业务场景&#xff0c;那 Kafka 作为一个高性能的分布式消息中间件&#xff0c;又是如何实现顺序消息的呢&#xff1f;本篇我们将对 Kafka 的顺序消息展开讨论。 Kafk…...

Kafka 之批量消息发送消费

前言&#xff1a; 前面我们分享了 Kafka 的一些基础知识&#xff0c;以及 Spring Boot 集成 Kafka 完成消息发送消费&#xff0c;本篇我们来分享一下 Kafka 的批量消息发送消费。 Kafka 系列文章传送门 Kafka 简介及核心概念讲解 Spring Boot 整合 Kafka 详解 Kafka Kafka…...

【大数据学习 | kafka】kafka的偏移量管理

1. 偏移量的概念 消费者在消费数据的时候需要将消费的记录存储到一个位置&#xff0c;防止因为消费者程序宕机而引起断点消费数据丢失问题&#xff0c;下一次可以按照相应的位置从kafka中找寻数据&#xff0c;这个消费位置记录称之为偏移量offset。 kafka0.9以前版本将偏移量信…...

实景三维赋能森林防灭火指挥调度智慧化

森林防灭火工作是保护森林资源和生态环境的重要任务。随着信息技术的发展&#xff0c;实景三维技术在森林防灭火指挥调度中的应用日益广泛&#xff0c;为提升防灭火工作的效率和效果提供了有力支持。 一、森林防灭火面临的挑战 森林火灾具有突发性强、破坏性大、蔓延速度快、…...

【C++课程学习】:string的模拟实现

&#x1f381;个人主页&#xff1a;我们的五年 &#x1f50d;系列专栏&#xff1a;C课程学习 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 一.string的主体框架&#xff1a; 二.string的分析&#xff1a; &#x1f354;构造函数和析构函数&a…...

Linux(VMware + CentOS )设置固定ip

需求&#xff1a;设置ip为 192.168.88.130 先关闭虚拟机 启动虚拟机 查看当前自动获取的ip 使用 FinalShell 通过 ssh 服务远程登录系统&#xff0c;更换到 root 用户 修改ip配置文件 vim /etc/sysconfig/network-scripts/ifcfg-ens33 重启网卡 systemctl restart network …...

安卓 android studio各版本下载地址(官方)

https://developer.android.google.cn/studio/archive 别用中文&#xff0c;右上角的语言切换成英文...

如何在一个 Docker 容器中运行多个进程 ?

在容器化的世界里&#xff0c;Docker 彻底改变了开发人员构建、发布和运行应用程序的方式。Docker 容器封装了运行应用程序所需的所有依赖项&#xff0c;使其易于跨不同环境一致地部署。然而&#xff0c;在单个 Docker 容器中管理多个进程可能具有挑战性&#xff0c;这就是 Sup…...

poetry 配置多个cuda环境心得

操作系统&#xff1a;ubuntu22.04 LTS python版本&#xff1a;3.12.7 最近学习了用poetry配置python虚拟环境&#xff0c;当为不同的项目配置cuda时&#xff0c;会遇到不同的项目使用的cuda版本不一致的情况。 像torch 这样的库&#xff0c;它们会对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&#xff1a; 组件要求存储SQL Server 要求最少 6 GB 的可用硬盘驱动器空间。 磁盘空间要求随…...

“众店模式”:创新驱动下的商业新生态

在数字化浪潮的推动下&#xff0c;传统商业模式正经历着前所未有的转型。“众店模式”作为一种新兴的商业模式&#xff0c;以其独特的商业逻辑和创新的玩法&#xff0c;为商家和消费者构建了一个共赢的商业新生态。 一、“众店模式”的核心构成 “众店模式”的成功&#xff0…...

54. 螺旋矩阵

https://leetcode.cn/problems/spiral-matrix/description/?envTypestudy-plan-v2&envIdtop-100-liked观察示例中的输出轨迹我们可以想到如下设计&#xff1a; 1.在朝某一方向行进到头后的改变方向是确定的&#xff0c;左->下&#xff0c;下->右&#xff0c;右->…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构

React 实战项目&#xff1a;微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇&#xff01;在前 29 篇文章中&#xff0c;我们从 React 的基础概念逐步深入到高级技巧&#xff0c;涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...

ZYNQ学习记录FPGA(二)Verilog语言

一、Verilog简介 1.1 HDL&#xff08;Hardware Description language&#xff09; 在解释HDL之前&#xff0c;先来了解一下数字系统设计的流程&#xff1a;逻辑设计 -> 电路实现 -> 系统验证。 逻辑设计又称前端&#xff0c;在这个过程中就需要用到HDL&#xff0c;正文…...

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

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

基于小程序老人监护管理系统源码数据库文档

摘 要 近年来&#xff0c;随着我国人口老龄化问题日益严重&#xff0c;独居和居住养老机构的的老年人数量越来越多。而随着老年人数量的逐步增长&#xff0c;随之而来的是日益突出的老年人问题&#xff0c;尤其是老年人的健康问题&#xff0c;尤其是老年人产生健康问题后&…...

el-amap-bezier-curve运用及线弧度设置

文章目录 简介示例线弧度属性主要弧度相关属性其他相关样式属性完整示例链接简介 ‌el-amap-bezier-curve 是 Vue-Amap 组件库中的一个组件,用于在 高德地图 上绘制贝塞尔曲线。‌ 基本用法属性path定义曲线的路径,可以是多个弧线段的组合。stroke-weight线条的宽度。stroke…...