|
| 1 | +packagemedium; |
| 2 | +/**213. House Robber II QuestionEditorial Solution My Submissions |
| 3 | +Total Accepted: 34216 |
| 4 | +Total Submissions: 107734 |
| 5 | +Difficulty: Medium |
| 6 | +Note: This is an extension of House Robber. |
| 7 | +
|
| 8 | +After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street. |
| 9 | +
|
| 10 | +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. |
| 11 | +
|
| 12 | +Credits: |
| 13 | +Special thanks to @Freezen for adding this problem and creating all test cases.*/ |
| 14 | +publicclassHouseRobberII { |
| 15 | + |
| 16 | +/**Another dp problem: |
| 17 | + * separate them into two cases: |
| 18 | + * 1. rob from house 1 to n-1, get max1 |
| 19 | + * 2. rob from house 2 to n, get max2 |
| 20 | + * take the max from the above two max*/ |
| 21 | +publicintrob(int[]nums) { |
| 22 | +if(nums ==null ||nums.length ==0)return0; |
| 23 | +if(nums.length ==1)returnnums[0]; |
| 24 | +if(nums.length ==2)returnMath.max(nums[0],nums[1]); |
| 25 | +int[]dp =newint[nums.length-1]; |
| 26 | + |
| 27 | +//rob 1 to n-1 |
| 28 | +dp[0] =nums[0]; |
| 29 | +dp[1] =Math.max(nums[0],nums[1]); |
| 30 | +for(inti =2;i <nums.length-1;i++){ |
| 31 | +dp[i] =Math.max(dp[i-2] +nums[i],dp[i-1]); |
| 32 | + } |
| 33 | +intprevMax =dp[nums.length-2]; |
| 34 | + |
| 35 | +//rob 2 to n |
| 36 | +dp =newint[nums.length-1]; |
| 37 | +dp[0] =nums[1]; |
| 38 | +dp[1] =Math.max(nums[1],nums[2]); |
| 39 | +for(inti =3;i <nums.length;i++){ |
| 40 | +dp[i-1] =Math.max(dp[i-3] +nums[i],dp[i-2]); |
| 41 | + } |
| 42 | +returnMath.max(prevMax,dp[nums.length-2]); |
| 43 | + } |
| 44 | + |
| 45 | +} |