力扣-213打家劫舍II(dp)

力扣-213打家劫舍II

1、题目

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

2、分析

1. 题目。这题与198打家劫舍唯一不同的就是首尾是相连的，所以遍历的时候要首不要尾，或者要尾不要首，就这两种情况。
2. 看到这个题目首先想到的是不能相邻，那么如果要偷其中i的一家，那么我们就需要考虑前面一家i-1就不能偷，i-2的一家就能够偷了，所以，我们大概能够知道这是一道动态规划问题。
3. 根据上面的分析，dp[i]就是我们偷当前i家的时候，最大金额数。那么我们可得地推公式为：dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])。
   初始化。
4. 遍历，两种情况，多个函数进行区间调用。

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