后端开发刷题 | 打家劫舍

embedded/2024/11/10 9:28:44/

描述

你是一个经验丰富的小偷,准备偷沿街的一排房间,每个房间都存有一定的现金,为了防止被发现,你不能偷相邻的两家,即,如果偷了第一家,就不能再偷第二家;如果偷了第二家,那么就不能偷第一家和第三家。

给定一个整数数组nums,数组中的元素表示每个房间存有的现金数额,请你计算在不被发现的前提下最多的偷窃金额。

数据范围:数组长度满足 1≤n≤2×105,数组中每个值满足 1≤num[i]≤5000

示例1

输入:

[1,2,3,4]

返回值:

6

说明:

最优方案是偷第 2,4 个房间   

示例2

输入:

[1,3,6]

返回值:

7

说明:

最优方案是偷第 1,3个房间   

示例3

输入:

[2,10,5]

返回值:

10

说明:

最优方案是偷第 2 个房间  

思路分析:

该题使用动态规划来解决,

具体做法:

  • step 1:用dp[i]表示长度为i的数组,最多能偷取到多少钱,只要每次转移状态逐渐累加就可以得到整个数组能偷取的钱。
  • step 2:(初始状态) 如果数组长度为1,只有一家人,肯定是把这家人偷了,收益最大,因此dp[1]=nums[0]。
  • step 3:(状态转移) 每次对于一个人家,我们选择偷他或者不偷他,如果我们选择偷那么前一家必定不能偷,因此累加的上上级的最多收益,同理如果选择不偷他,那我们最多可以累加上一级的收益。因此转移方程为dp[i]=max(dp[i−1],nums[i−1]+dp[i−2])。这里的i在dp中为数组长度,在nums中为下标。

图示:

alt

代码:

java">import java.util.*;public class Solution {/*** @param nums int整型一维数组 * @return int整型*/public int rob (int[] nums) {int[] dp=new int[nums.length+1];dp[1]=nums[0];for(int i=2;i<=nums.length;i++){dp[i]=Math.max(dp[i-1],nums[i-1]+dp[i-2]);}return dp[nums.length];}
}


http://www.ppmy.cn/embedded/113079.html

相关文章

ubuntu使用wireshark抓取数据

工具 aircrack-ng工具&#xff1b;wireshark工具 sudo apt-get install aircrack-ng2 sudo add-apt-repository ppa:wireshark-dev/stable sudo apt update sudo apt install -y wireshark使用 airmon-ng 执行ifconfig查看网卡 设置网卡为监听模式&#xff1a;sudo airmo…

Html css样式总结

1.Html css样式总结 1.1. 定位position 布局是html中非常重要的一部分&#xff0c;而定位在页面布局中也是使用频率很高的方法&#xff0c;本章节为定位在布局中的使用技巧和注意事项。   position定位有4个属性&#xff0c;分别是static(默认&#xff09;&#xff0c;absol…

已读论文创新点合集

系列文章目录 文章目录 系列文章目录一、《LAMM: Label Alignment for Multi-Modal Prompt Learning》二、《MaPLe: Multi-modal Prompt Learning》三、《Learning to Prompt for Vision-Language Models》CoOp 一、《LAMM: Label Alignment for Multi-Modal Prompt Learning》…

【30天玩转python】高级数据结构

高级数据结构 在 Python 中&#xff0c;除了基础的列表、元组、字典和集合等数据结构之外&#xff0c;还有一些更复杂和高级的数据结构。这些数据结构在解决特定问题时能够提供更好的性能和更强的功能。本节将介绍一些常用的高级数据结构&#xff0c;包括堆、队列、双端队列、…

C++笔记---多态

1. 多态的概念 多态(polymorphism)的概念&#xff1a;通俗来说&#xff0c;就是多种形态。 多态分为编译时多态(静态多态)和运行时多态(动态多态)&#xff0c;这里我们重点讲运行时多态&#xff0c;编译时多态(静态多态)和运行时多态(动态多态)。 编译时多态(静态多态)主要就…

CPU 和 GPU:为什么GPU更适合深度学习?

目录 什么是 CPU &#xff1f; 什么是 GPU &#xff1f; GPU vs CPU 差异性对比分析 GPU 是如何工作的 &#xff1f; GPU 与 CPU 是如何协同工作的 &#xff1f; GPU vs CPU 类型解析 GPU 应用于深度学习 什么是 CPU &#xff1f; CPU&#xff08;中央处理器&#xff09;…

用于稀疏自适应深度细化的掩码空间传播网络 CVPR2024

目录 Masked Spatial Propagation Network for Sparsity-Adaptive Depth Refinement &#xff08;CVPR 2024&#xff09;用于稀疏自适应深度细化的掩码空间传播网络1 介绍2 算法流程2.1 问题建模2.2 Guidance Network2.3 MSPN 模块 3 实验结果3.1 稀疏度自适应深度细化对比试验…

分享JavaScript中直接调用CSS中的类名

分享JavaScript中直接调用CSS中的类名 在现代的 JavaScript 框架&#xff08;如 React、Vue&#xff09;中&#xff0c;使用 CSS 模块&#xff08;CSS Modules&#xff09;是一种非常流行的方式。.module.css 文件扩展名代表的是 CSS 模块&#xff0c;它与普通的 CSS 文件不同…