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

相关文章

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体(数据库的定义)2.预加载preload3.添加关联的方法一、动态路由1

Python Selenium动态渲染页面和抓取的使用指南

《PythonSelenium动态渲染页面和抓取的使用指南》在Web数据采集领域,动态渲染页面已成为现代网站的主流形式,本文将从技术原理,环境配置,核心功能系统讲解Selenium在Python动态... 目录一、Selenium技术架构解析二、环境搭建与基础配置1. 组件安装2. 驱动配置3. 基础操作模

慢sql提前分析预警和动态sql替换-Mybatis-SQL

《慢sql提前分析预警和动态sql替换-Mybatis-SQL》为防止慢SQL问题而开发的MyBatis组件,该组件能够在开发、测试阶段自动分析SQL语句,并在出现慢SQL问题时通过Ducc配置实现动... 目录背景解决思路开源方案调研设计方案详细设计使用方法1、引入依赖jar包2、配置组件XML3、核心配

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删