83、动态规划-打家劫舍

2024-05-04 07:44
文章标签 动态 规划 83 打家劫舍

本文主要是介绍83、动态规划-打家劫舍,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

思路:

首先使用递归方式求出最优解。从每个房屋开始,分别考虑偷与不偷两种情况,然后递归地对后续的房屋做同样的决策。这种方法确保了可以找到在不触发警报的情况下可能的最高金额。

代码如下:

public static int rob(int[] nums) {if (nums == null || nums.length == 0) {return 0;  // 如果没有房屋可偷,则返回0}// 递归求解最大金额return process(nums, 0, nums.length);
}private static int process(int[] nums, int index, int N) {if (index >= N) {return 0;  // 超出数组范围,返回0}// 偷当前房屋并跳过下一个房屋int p1 = nums[index] + process(nums, index + 2, N);// 不偷当前房屋,考虑下一个房屋int p2 = process(nums, index + 1, N);// 返回两种方案中的最大值return Math.max(p1, p2);
}

但是递归方式会有重复计算,知道了思路来改成动态规划就很容易。dp[N]=0,超出长度,dp[n-1]=nums[n-1]表示从n-1开始最优抢多少金额,那只能抢一家。然后开始递归。dp状态转移方程就是Math.max(nums[i] + dp[i + 2], dp[i + 1]);代码如下:

class Solution {public static int rob(int[] nums) {// 检查输入数组是否为空,如果为空或长度为0,则直接返回0,因为没有什么可以偷的if (nums == null || nums.length == 0) {return 0;}// 获取数组的长度,即房屋的数量int N = nums.length; // 创建一个动态规划数组,长度为N+1,用来存储到每个房屋为止的最大偷窃金额int[] dp = new int[N + 1]; // 数组最后一个元素设为0,表示超过最后一个房屋后没有可偷的金额dp[N] = 0;  // 初始化最后一间房屋的情况,只有一个选择,就是偷这间房屋dp[N - 1] = nums[N - 1];  // 从倒数第二个房间开始向前计算每个房间的最大偷窃金额for (int i = N - 2; i >= 0; i--) {// 如果偷当前房屋i,那么下一个可偷的房屋是i+2,总金额是当前房屋的金额加上dp[i+2]int p1 = nums[i] + dp[i + 2]; // 如果不偷当前房屋i,那么考虑从下一个房屋i+1开始的最大金额int p2 = dp[i + 1];  // 对于当前房屋i,选择偷与不偷的最大值作为dp[i]的值dp[i] = Math.max(p1, p2);}// 返回从第一间房屋开始偷窃的最大金额,即dp数组的第一个元素return dp[0];
}}

这篇关于83、动态规划-打家劫舍的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/958683

相关文章

Java使用POI-TL和JFreeChart动态生成Word报告

《Java使用POI-TL和JFreeChart动态生成Word报告》本文介绍了使用POI-TL和JFreeChart生成包含动态数据和图表的Word报告的方法,并分享了实际开发中的踩坑经验,通过代码... 目录前言一、需求背景二、方案分析三、 POI-TL + JFreeChart 实现3.1 Maven

Java导出Excel动态表头的示例详解

《Java导出Excel动态表头的示例详解》这篇文章主要为大家详细介绍了Java导出Excel动态表头的相关知识,文中的示例代码简洁易懂,具有一定的借鉴价值,有需要的小伙伴可以了解下... 目录前言一、效果展示二、代码实现1.固定头实体类2.动态头实现3.导出动态头前言本文只记录大致思路以及做法,代码不进

vue基于ElementUI动态设置表格高度的3种方法

《vue基于ElementUI动态设置表格高度的3种方法》ElementUI+vue动态设置表格高度的几种方法,抛砖引玉,还有其它方法动态设置表格高度,大家可以开动脑筋... 方法一、css + js的形式这个方法需要在表格外层设置一个div,原理是将表格的高度设置成外层div的高度,所以外层的div需要

SpringBoot实现动态插拔的AOP的完整案例

《SpringBoot实现动态插拔的AOP的完整案例》在现代软件开发中,面向切面编程(AOP)是一种非常重要的技术,能够有效实现日志记录、安全控制、性能监控等横切关注点的分离,在传统的AOP实现中,切... 目录引言一、AOP 概述1.1 什么是 AOP1.2 AOP 的典型应用场景1.3 为什么需要动态插

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式(对象添加:情景一)2.动态添加一个class样式(字符串添加:情

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R

如何用Python绘制简易动态圣诞树

《如何用Python绘制简易动态圣诞树》这篇文章主要给大家介绍了关于如何用Python绘制简易动态圣诞树,文中讲解了如何通过编写代码来实现特定的效果,包括代码的编写技巧和效果的展示,需要的朋友可以参考... 目录代码:效果:总结 代码:import randomimport timefrom math

Java中JSON字符串反序列化(动态泛型)

《Java中JSON字符串反序列化(动态泛型)》文章讨论了在定时任务中使用反射调用目标对象时处理动态参数的问题,通过将方法参数存储为JSON字符串并进行反序列化,可以实现动态调用,然而,这种方式容易导... 需求:定时任务扫描,反射调用目标对象,但是,方法的传参不是固定的。方案一:将方法参数存成jsON字

.NET利用C#字节流动态操作Excel文件

《.NET利用C#字节流动态操作Excel文件》在.NET开发中,通过字节流动态操作Excel文件提供了一种高效且灵活的方式处理数据,本文将演示如何在.NET平台使用C#通过字节流创建,读取,编辑及保... 目录用C#创建并保存Excel工作簿为字节流用C#通过字节流直接读取Excel文件数据用C#通过字节

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作