:-: 9.4 打家劫舍 II * * * * * **题干：** 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈（环状），这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。 示例 1: ~~~ 输入: [2,3,2] 输出: 3 解释: 你不能先偷窃 1 号房屋（金额 = 2），再偷窃 3 号房屋（金额 = 2）,因为 它们是相邻的。 ~~~ 示例 2: ~~~ 输入: [1,2,3,1] 输出: 4 解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。 ~~~ **题目分析：** 解题思路是和打家劫舍 I是一样的，只不过偷第一件房屋和偷最后一间房屋不能同时存在，我们需要分两种情况来考虑（分抢劫范围包含或不包含第一个的房屋），如果抢劫范围包含第一个房屋，思路和打家劫舍 I一样，如果有n个房屋，只考虑前n - 1个房屋，如果抢劫范围不包含第一个房屋，如果有n个房屋，只考虑第一房屋后的n - 1个房屋，再将两种情况最后的金额取最大值。动态规划方程和打家劫舍 I是一样的：f(n) = Math.max(nums[i]+f(n-2),f(n-1));。 **新手有可能遇到的解题思路陷阱：** 考虑到了偷盗了第一个房屋，不能头套最后一个房屋，却忽略了第二个房屋也是可以和最后一个房屋结合被偷盗；或者当偷盗范围不包含第一个房屋时，第二个，第三个房屋是起始项，而不是在偷盗范围不包含第一个房屋时，单单第二个房屋是起始项。 **解题思路分析以及代码实现：** 第一种思路：迭代法，双循环，顺序走。当数组长度为2的时候，返回Math.max(nums[0], nums[1])；当数组长度为3的时候，其实应该去经历循环判断，但是我们能够一眼看出，这根本没必要，前两个数谁也得不到最后一个数，何必去做判断，浪费资源。 第一种思路代码： ~~~ public static int rob(int[] nums) { if (nums.length < 1 || nums == null) { return 0; } int length = nums.length; if (length < 2) { return nums[0]; } if (length == 3 || length == 2) { return Math.max(nums[0], nums[1]); } int sum = 0; int sum1 = nums[0]; int sum2 = Math.max(nums[0], nums[1]); int i = 2; while (i < length - 1) { sum = Math.max(sum1 + nums[i], sum2); sum1 = sum2; sum2 = sum; i++; } int sum3 = 0; int sum4 = nums[1]; int sum5 = Math.max(nums[1], nums[2]); int j = 3; while (j < length) { sum3 = Math.max(sum4 + nums[j], sum5); sum4 = sum5; sum5 = sum3; j++; } return Math.max(sum2, sum5); } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(1)。 第二种思路：迭代法，单循环，加判断，此次优化不为复杂度，而是优化可读性等。 第二种思路代码： ~~~ public static int rob(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0]; int dp1 = nums[0], dp2 = Math.max(dp1, nums[1]); int dpS = dp2; if (nums.length == 2 || nums.length == 3) return dp2; int dp3 = nums[1], dp4 = Math.max(dp3, nums[2]); int dpE = dp4; for (int i = 2; i < nums.length; i++) { if (i != nums.length - 1) { dpS = Math.max(dp1 + nums[i], dp2); dp1 = dp2; dp2 = dpS; } if (i != 2) { dpE = Math.max(dp3 + nums[i], dp4); dp3 = dp4; dp4 = dpE; } } return Math.max(dpS, dpE); } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(1)。 衍生版本代码： ~~~ public int rob(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0]; if (nums.length == 2 || nums.length == 3) return Math.max(nums[0], nums[1]); return Math.max(robsub(nums, 0, nums.length - 2), robsub(nums, 1, nums.length - 1)); } private int robsub(int[] nums, int top, int tail) { int sum = 0; int sum1 = nums[top]; int sum2 = Math.max(nums[top], nums[top + 1]); for (int i = 2 + top; i <= tail; i++) { sum = Math.max(sum1 + nums[i], sum2); sum1 = sum2; sum2 = sum; } return sum2; } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(1)。 第三种思路：数组法 第三种思路代码： ~~~ public int rob(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0]; if (nums.length == 2 || nums.length == 3) return Math.max(nums[0], nums[1]); return Math.max(robsub(nums, 0, nums.length - 2), robsub(nums, 1, nums.length - 1)); } private int robsub(int[] nums, int top, int tail) { int d[] = new int[tail - top + 1]; int n = tail - top + 1; d[0] = nums[top]; d[1] = Math.max(nums[top], nums[top + 1]); for (int i = 2; i < n; i++) { d[i] = Math.max(d[i - 2] + nums[top + i], d[i - 1]); } return d[n - 1]; } ~~~ **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(n)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**