题目:
难度:Middle
相关话题:动态规划
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈, 这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下, 能够偷窃到的最高金额。
示例1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
if (nums.length == 1) return nums[0];
return Math.max(maxProfit(nums, 0, nums.length - 2), maxProfit(nums, 1, nums.length - 1));
function maxProfit(nums,lo,hi){
let last_stole=0,last_notStole=0,
cur_stole=0,cur_notStole=0
for(let i=lo;i<=hi;i++){
cur_stole=last_notStole+nums[i]
cur_notStole=Math.max(last_stole,last_notStole)
last_stole=cur_stole
last_notStole=cur_notStole
}
return Math.max(cur_stole,cur_notStole)
}
};