沈阳行业网站建设,空包网站建设属于哪类,店铺logo图片大全,网站建设的战略作用打家劫舍2
力扣原题链接
问题描述
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋#xff0c;每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈#xff0c;这意味着第一个房屋和最后一个房屋是紧挨着的。同时#xff0c;相邻的房屋装有相互连通的防盗系统计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下今晚能够偷窃到的最高金额。
示例
示例 1
输入nums [2,3,2]
输出3
解释你不能先偷窃 1 号房屋金额 2然后偷窃 3 号房屋金额 2, 因为他们是相邻的。示例 2
输入nums [1,2,3,1]
输出4
解释你可以先偷窃 1 号房屋金额 1然后偷窃 3 号房屋金额 3。偷窃到的最高金额 1 3 4 。示例 3
输入nums [1,2,3]
输出3分析
这是一个环形动态规划问题。由于第一个房屋和最后一个房屋是相邻的因此偷窃第一个房屋就不能偷窃最后一个房屋偷窃最后一个房屋就不能偷窃第一个房屋。因此我们可以将问题转化为两个子问题
不偷窃第一个房屋偷窃第二个房屋到最后一个房屋之间的房屋。不偷窃最后一个房屋偷窃第一个房屋到倒数第二个房屋之间的房屋。
对于每个子问题可以使用动态规划求解。
状态定义
定义一个一维动态规划数组 dp其中 dp[i] 表示偷窃第一个房屋到第 i 个房屋时的最高金额。
状态转移方程
对于每个房屋 nums[i]有两种选择偷窃该房屋或者不偷窃该房屋。状态转移方程为
dp[i] max(dp[i-1], dp[i-2] nums[i])初始化
需要对动态规划数组进行初始化。初始时dp[0] nums[0]dp[1] max(nums[0], nums[1])。
Java解题
class Solution {// 主函数计算环形盗窃计划的最大金额public int rob(int[] nums) {// 如果只有一个房屋则直接返回该房屋的金额if (nums.length 1) return nums[0];// 分别计算不偷窃第一个房屋和不偷窃最后一个房屋的最大金额取两者的较大值return Math.max(robRange(nums, 0, nums.length - 2), robRange(nums, 1, nums.length - 1));}// 辅助函数计算偷窃指定范围内房屋的最大金额private int robRange(int[] nums, int start, int end) {// 初始化前一个房屋的最大金额和当前房屋的最大金额int prevMax 0;int currMax 0;// 遍历指定范围内的房屋for (int i start; i end; i) {// 临时保存当前房屋的最大金额int temp currMax;// 更新当前房屋的最大金额选择偷窃当前房屋或者不偷窃当前房屋currMax Math.max(prevMax nums[i], currMax);// 更新前一个房屋的最大金额prevMax temp;}// 返回偷窃指定范围内房屋的最大金额return currMax;}
}
总结
通过环形动态规划的思想我们可以解决这个问题。首先将问题分解为两个子问题然后对每个子问题使用动态规划求解最终返回两个子问题的最大值。
