打家劫舍 II

题目

思路

• 总体思路与打家劫舍类似，只是要把环拆成两个队列，一个是从0到n-1，另一个是从1到n，然后返回两个结果最大的。或者记住它是否使用了第一个元素

  代码

  ```java //1.暴力递归 public int rob(int[] nums) {

    int len = nums.length;
    if (len == 0) return 0;
    return Math.max(recur(nums, len - 3, 1) + nums[len - 1], recur(nums, len - 2, 0));

  }

  public int recur(int[] nums , int i, int end) {

    if (i < end) return 0;
    return Math.max(recur(nums, i - 2, end) + nums[i], recur(nums, i - 1, end));
  

  }

  //2.动态规划 public int rob(int[] nums) {

    int len = nums.length;
    if (len == 0) return 0;
    if (len == 1) return nums[0];
    int p1 = nums[0], p2 = Math.max(nums[0], nums[1]);
    int p3 = 0, p4 = 0, t = 0;
    for (int i = 2; i < len; i++) {
        if (i < len - 1) {
            t = Math.max(p1 + nums[i], p2);
            p1 = p2;
            p2 = t;
        }
        if (i == 3) {
            p3 = nums[1];
            p4 = Math.max(nums[1], nums[2]);
        }
        if (i > 2) {
            t = Math.max(p3 + nums[i], p4);
            p3 = p4;
            p4 = t;
       }
    }
    return p1 = p2 > p4 ? p2 : p4;
  

  }

``` 打家劫舍 II