简述dw网站建设步骤,品牌策划案例ppt,网站备案的要求是什么,咸阳网站制作力扣-213打家劫舍II
1、题目
213. 打家劫舍 II
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋#xff0c;每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 #xff0c;这意味着第一个房屋和最后一个房屋是紧挨着的。同时#xff0c;相邻的房屋装有相互连通…力扣-213打家劫舍II
1、题目
213. 打家劫舍 II
你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
示例 1
输入nums [2,3,2]
输出3
解释你不能先偷窃 1 号房屋金额 2然后偷窃 3 号房屋金额 2, 因为他们是相邻的。2、分析
题目。这题与198打家劫舍唯一不同的就是首尾是相连的所以遍历的时候要首不要尾或者要尾不要首就这两种情况。看到这个题目首先想到的是不能相邻那么如果要偷其中i的一家那么我们就需要考虑前面一家i-1就不能偷i-2的一家就能够偷了所以我们大概能够知道这是一道动态规划问题。根据上面的分析dp[i]就是我们偷当前i家的时候最大金额数。那么我们可得地推公式为dp[i] Math.max(dp[i - 1], dp[i - 2] nums[i])。 初始化。遍历两种情况多个函数进行区间调用。
3、代码及注释
class Solution {public int rob(int[] nums) {// 1.第一种就是要最后一个房屋// 2.第二种就是不要最后一个房屋if (nums.length 0) return 0;if (nums.length 1) return nums[0];if (nums.length 2) return Math.max(nums[0], nums[1]);return Math.max(robRange(nums, 0, nums.length - 1), robRange(nums, 1, nums.length));}public int robRange(int[] nums, int start, int end){int[] dp new int[end];dp[start] nums[start];dp[start 1] Math.max(nums[start 1], dp[start]);for (int i start 2; i end; i){dp[i] Math.max(dp[i - 1], dp[i - 2] nums[i]);}return dp[end - 1];}
}4、练习
力扣题目链接213. 打家劫舍 II
