You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
你是一名专业的强盗，计划抢劫沿街的房屋。 每个房子都藏有一定数量的钱。 这个地方的所有房屋都围成一圈。 这意味着第一个房子是最后一个的邻居。 与此同时，相邻的房屋有相连的保安系统，如果两个相邻的房屋在同一天晚上闯入，它会自动联系警方。
给出一份代表每个房屋的金额的非负整数列表，确定你可以在没有提醒警方的情况下抢劫的最高金额。
Example 1:
Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
because they are adjacent houses.
Example 2:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
思路:
这个问题可以转化为求从nums[0]抢到nums[n-2]和nums[1]抢到nums[n-1]的最大值.
JavaScript版代码:
/**
* @param {number[]} nums
* @return {number}
*/
const rob = function(nums) {
const len=nums.length;
if(len<1){
return 0;
}
if(len===1){
return nums[0];
}
if(len===2){
return Math.max(nums[0],nums[1]);
}
return Math.max(robe(nums.slice(1)),robe(nums.slice(0,len-1)));
};
const robe = function(nums) {
let n = nums.length;
// if(n == 0) return 0;
// if(n == 1) return nums[0];
if(n == 2) return Math.max(nums[0], nums[1]);
let dp = [];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
dp[2] = Math.max(nums[0]+nums[2], nums[1]);
for(let i = 3; i < n; i++){
dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[n-1];
};
robe函数是 House Robber(easy) 的解,在这里可以用到,这道题的思路就是把复杂的问题转化为简单问题.