打家劫舍II

TIP

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

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

思路

对于一个数组，成环的话主要有如下三种情况：

情况一：考虑不包含首尾元素

情况二：考虑包含首元素，不包含尾元素

情况三：考虑包含尾元素，不包含首元素

注意我这里用的是"考虑"，例如情况三，虽然是考虑包含尾元素，但不一定要选尾部元素！对于情况三，取nums[1] 和 nums[3]就是最大的。

而情况二和情况三都包含了情况一了，所以只考虑情况二和情况三就可以了。

var rob = function(nums) {
    if(nums.length===1) return nums[0]
    //情况二：考虑首元素
    let nums1 = nums.slice(0,nums.length-1)
    let first = rob1(nums1)
    //情况三：考虑尾元素
    let nums2 = nums.slice(1,nums.length)
    let last = rob1(nums2)
    return Math.max(first,last)
};

// 打家劫舍I
var rob1 = function(newnums) {
    let dp = []
    dp[0] = newnums[0]
    dp[1] = Math.max(newnums[0],newnums[1])
    for(let i=2;i<newnums.length;i++){
        dp[i] = Math.max(dp[i-2]+newnums[i],dp[i-1])
    }
    return dp[newnums.length-1]
};

打家劫舍II ​

思路 ​

打家劫舍II

思路