Solved
Medium
Topics
Companies
Hint
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 a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [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: nums = [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.
Example 3:
Input: nums = [1,2,3]
Output: 3
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 1000这道题和前面这道题不同的特点是，首尾相连，所以首尾也是相邻的。 那就是首尾不能同时选。 我们可以用 1 的方法做两次搜索，第一次是从0到倒数第二个，第二次从1 到倒数最后一个。
class Solution {
public int rob(int[] nums) {
dp = new int[nums.length];
if(nums.length == 1) return nums[0];
Arrays.fill(dp,-1);
int ans1 = dfs(0,nums.length- 1,nums);
//注意要重置一下dp，第一次搜完之后
Arrays.fill(dp,-1);
int ans2 = dfs(1,nums.length,nums);
return Math.max(ans1,ans2);
}
int []dp;
int dfs(int index, int end , int[] nums){
if(index >= end ) return 0;
if(dp[index]!=-1) return dp[index];
return dp[index]=Math.max(dfs(index+1,end,nums), dfs(index+2,end,nums) + nums[index]);
}
}