数据结构与算法之打家劫舍(一)动态规划思想
动态规划里面一部题目打家劫舍是一类经典的算法题目之一,他有各种各样的变式,这一篇文章和大家分享一下打家劫舍最基础的一道题目,掌握这一道题目,为下一道题目打下基础。我们直接进入正题。
一.题目


大家如果刚接触这样的题目,会有点困惑,当前的状态我是偷还是不偷呢?
仔细一想,当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。
所以这里就更感觉到,当前状态和前面状态会有一种依赖关系,那么这种依赖关系都是动规的递推公式。
当然以上是大概思路,打家劫舍是dp解决的经典问题,接下来我们来动规五部曲分析如下:
二.动态规划五部曲
确定dp数组(dp table)以及下标的含义
dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。
2.确定递推公式
决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间,那么dp[i] = dp[i - 2] + nums[i] ,即:第i-1房一定是不考虑的,找出 下标i-2(包括i-2)以内的房屋,最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
如果不偷第i房间,那么dp[i] = dp[i - 1],即考 虑i-1房,(注意这里是考虑,并不是一定要偷i-1房,这是很多人容易混淆的点)
然后dp[i]取最大值,即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
3.dp数组如何初始化
从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出,递推公式的基础就是dp[0] 和 dp[1]
从dp[i]的定义上来讲,dp[0] 一定是 nums[0],dp[1]就是nums[0]和nums[1]的最大值即:dp[1] = max(nums[0], nums[1]);
代码如下:
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);4.确定遍历顺序
dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从前到后遍历!
代码如下:
for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}5.举例推导dp数组
以示例二,输入[2,7,9,3,1]为例。

红框dp[nums.size() - 1]为结果。
以上分析完毕,C++代码如下:
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());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];}
};Java代码如下:
// 动态规划
class Solution {public int rob(int[] nums) {if (nums == null || nums.length == 0) return 0;if (nums.length == 1) return nums[0];int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Math.max(dp[0], nums[1]);for (int i = 2; i < nums.length; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[nums.length - 1];}
}总结:
打家劫舍是DP解决的经典题目,这道题也是打家劫舍入门级题目,后面我们还会变种方式来打劫的。
做算法题最重要的就是坚持。大家加油!
相关文章:
数据结构与算法之打家劫舍(一)动态规划思想
动态规划里面一部题目打家劫舍是一类经典的算法题目之一,他有各种各样的变式,这一篇文章和大家分享一下打家劫舍最基础的一道题目,掌握这一道题目,为下一道题目打下基础。我们直接进入正题。一.题目大家如果刚接触这样的题目&…...
无人驾驶路径规划论文简要
A Review of Motion Planning Techniques for Automated Vehicles综述和分类0Motion Planning for Autonomous Driving with a Conformal Spatiotemporal Lattice从unstructured环境向structured环境的拓展,同时还从state lattice拓展到了spatiotemporal lattice从而…...
C++ sort()函数和priority_queue容器中比较函数的区别
普通的queue是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。priority_queue中元素被赋予优先级。在创建的时候根据优先级进行了按照从大到小或者从小到大进行了自动排列(大顶堆or小顶堆)。可以以O(log n) 的效率查找…...
STM32开发(14)----CubeMX配置ADC
CubeMX配置ADC前言一、什么是ADC?二、实验过程1.单通道ADC采集STM32CubeMX配置代码实现2.多通道ADC采样(非DMA)STM32CubeMX配置代码实现3.多通道ADC采样(DMA)STM32CubeMX配置代码实现总结前言 本章介绍使用STM32CubeMX对ADC进行配置的方法&a…...
Simple RNN、LSTM、GRU序列模型原理
一。循环神经网络RNN 用于处理序列数据的神经网络就叫循环神经网络。序列数据说直白点就是随时间变化的数据,循环神经网络它能够根据这种数据推出下文结果。RNN是通过嵌含前一时刻的状态信息实行训练的。 RNN神经网络有3个变种,分别为Simple RNN、LSTM、…...
【原创】java+swing+mysql生肖星座查询系统设计与实现
今天我们来开发一个比较有趣的系统,根据生日查询生肖星座,输入生日,系统根据这个日期自动计算出生肖和星座信息反馈到界面。我们还是使用javaswingmysql去实现这样的一个系统。 功能分析: 生肖星座查询系统,顾名思义…...
CentOS 环境 OpneSIPS 3.1 版本安装及使用
文章目录1. OpenSIPS 源码下载2. 工具准备3. 编译安装4. opensips-cli 工具安装5. 启动 OpenSIPS 实例1. OpenSIPS 源码下载 使用以下命令即可下载 OpenSIPS 的源码,笔者下载的是比较稳定的 3.1 版本,读者有兴趣也可前往 官方传送门 sudo git clone htt…...
SQL95 从 Products 表中检索所有的产品名称以及对应的销售总数
描述 Products 表中检索所有的产品名称:prod_name、产品id:prod_idprod_idprod_namea0001egga0002socketsa0013coffeea0003colaOrderItems代表订单商品表,订单产品:prod_id、售出数量:quantityprod_idquantitya0001105…...
平时技术积累很少,面试时又会问很多这个难题怎么破?别慌,没事看看这份Java面试指南,解决你的小烦恼!
前言技术面试是每个程序员都需要去经历的事情,随着行业的发展,新技术的不断迭代,技术面试的难度也越来越高,但是对于大多数程序员来说,工作的主要内容只是去实现各种业务逻辑,涉及的技术难度并不高…...
SQL Server 数据库的备份
为何要备份数据库? 备份 SQL Server 数据库、在备份上运行测试还原过程以及在另一个安全位置存储备份副本可防止可能的灾难性数据丢失。 备份是保护数据的唯一方法 。 使用有效的数据库备份,可从多种故障中恢复数据,例如: 介质…...
NCNN Conv量化详解1
1. NCNN的Conv量化计算流程 正常的fp32计算中,一个Conv的计算流程如下: 在NCNN Conv进行Int8计算时,计算流程如下: NCNN首先将输入(bottom_blob)和权重(weight_blob)量化成INT8,在INT8下计算卷积,然后反量化到fp32,再和未量化的bias相加,得到输出(top_blob) 输入和…...
Redis大key多key拆分方案
业务场景中经常会有各种大key多key的情况, 比如:1:单个简单的key存储的value很大2:hash, set,zset,list 中存储过多的元素(以万为单位)3:一个集群存储了上亿的…...
python的类如何使用?兔c同学一篇关于python类的博文概述
本章内容如目录 所示: 文章目录1. 创建和使用类1.1 创建第一个python 类1.2 版本差异1.3 根据类创建实例1. 访问属性2. 调用方法3. 创建多个实例2. 使用类和实例2.1 给属性指定默认值2.2 修改属性的值3. 继承3.1 子类的 __init __()3.2 给子类定义属性和方法3.3 重写…...
Day60 动态规划总结
647. 回文子串 回文的做法注定我们得从里面入手,逐渐扩散到边界 初始化:准备一个ans,找到一个回文子串加一个 dp [[0] * n for _ in range(n)]ans 0 遍历公式: 当s[i]s[j]的时候,只要里面还是回文串,就能…...
UVM仿真环境搭建
环境 本实验使用环境为: Win10平台下的Modelsim SE-64 2019.2 代码 dut代码: module dut(clk,rst_n, rxd,rx_dv,txd,tx_en); input clk; input rst_n; input[7:0] rxd; input rx_dv; output [7:0] txd; output tx_en;reg[7:0] txd; reg tx_en;always…...
Azure AI基础到实战(C#2022)-认知服务(1)
目录 Azure 认知服务概述计算机视觉概述数据隐私和安全性计算机视觉快速入门光学字符识别 (OCR)OCR APIOCR 常用功能Azure 门户准备两种部署方式OCR项目实战之车牌识别Azure 认知服务概述 Azure 认知服务是基于云的人工智能 (AI) 服务,可帮助开发人员在不具备直接的 AI 或数据…...
光栅化Triangles(笔记)
field of view (可见区域) 该角度越大,需要透视投影的角度越大,成像显示的内容越多 有Y值,则可得出成像范围 屏幕: 典型的光栅处理设备所有像素都被表示为x,y坐标轴形式 3D方块成像步骤: 先将其所在平面化为 与屏幕等长等宽的形式: 如何将一个三角形拆成像素?采样…...
【Oarcle】如何显示日本年号的日期格式 ?
语句大于一切,还需要语言吗? 1. SELECT TO_CHAR(SYSDATE,EEYY/MM/DD,NLS_CALENDAR JAPANESE IMPERIAL) from dual;结果是: 令和05/02/25 Oracle SQL文中,年月日的显示,一定要使用双引号括起来,如 select…...
57_Pandas中的json_normalize将字典列表转换为DataFrame
57_Pandas中的json_normalize将字典列表转换为DataFrame 可以使用 pandas.json_normalize() 将具有公共键的字典列表转换为 pandas.DataFrame。 由于它是一种常用的JSON格式,可以通过Web API获取,所以能够将其转换为pandas.DataFrame是非常方便的。 在…...
OpenAPI SDK组件之javassist字节码
javassist介绍 Javassist是一个开源的分析、编辑和创建Java字节码的类库,主要优点是简单,不需要了解虚拟机指令,就能动态改变类的结构,或者动态生成类。 apisdk应用javassist 在apisdk中主要依靠javassist增强开发者声明的开放…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
高考志愿填报管理系统---开发介绍
高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发,采用现代化的Web技术,为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## 📋 系统概述 ### 🎯 系统定…...
