当前位置: 首页> 健康> 养生 > 天元集团建设有限公司简介_中山网站建设推荐_百度客服中心电话_seo推广软件品牌

天元集团建设有限公司简介_中山网站建设推荐_百度客服中心电话_seo推广软件品牌

时间:2025/7/9 3:28:06来源:https://blog.csdn.net/xxjiaz/article/details/146189052 浏览次数:1次
天元集团建设有限公司简介_中山网站建设推荐_百度客服中心电话_seo推广软件品牌

#蓝桥#JAVA#打家劫舍

题目描述

一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组 nums ,请计算 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 1:

输入:nums = [1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入:nums = [2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解题方法

动态规划
首先考虑最简单的情况。如果只有一间房屋,则偷窃该房屋,可以偷窃到最高总金额。如果只有两间房屋,则由于两间房屋相邻,不能同时偷窃,只能偷窃其中的一间房屋,因此选择其中金额较高的房屋进行偷窃,可以偷窃到最高总金额。

如果房屋数量大于两间,应该如何计算能够偷窃到的最高总金额呢?对于第 k (k>2) 间房屋,有两个选项:

偷窃第 k 间房屋,那么就不能偷窃第 k−1 间房屋,偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。

不偷窃第 k 间房屋,偷窃总金额为前 k−1 间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项,该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。

用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额,那么就有如下的状态转移方程:

dp[i]=max(dp[i−2]+nums[i],dp[i−1])
边界条件为:

dp[0]=nums[0]只有一间房屋,则偷窃该房屋
dp[1]=max(nums[0],nums[1])只有两间房屋,选择其中金额较高的房屋进行偷窃
最终的答案即为 dp[n−1],其中 n 是数组的长度。

class Solution {public int rob(int[] nums) {if(nums == null || nums.length == 0){return 0;}int length = nums.length; if(length == 1){return nums[0];}int[] dp = new int[length];dp[0] = nums[0];dp[1] = Math.max(nums[0],nums[1]);for(int i = 2;i < length;i++){dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);}return dp[length-1];}
}

关键字:天元集团建设有限公司简介_中山网站建设推荐_百度客服中心电话_seo推广软件品牌

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: