# Leetcode: House Robber II

House Robber Similar Problems:

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.

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```// Blog link: https://code.dennyzhang.com/house-robber-ii
// Basic Ideas: dynamic programming
// dp[i]: with nums selected, include nums[i]
// dp[i]: with nums selected, exclude nums[i]
// dp[i]: with nums not selected, include nums[i]
// dp[i]: with nums not selected, exclude nums[i]
// Complexity: Time O(n), Space O(n)
func rob(nums []int) int {
if len(nums) == 0 { return 0 }
if len(nums) == 1 { return nums }

dp := make([][]int, len(nums))
for i, _ := range nums {
if i == 0 {
dp = []int{nums, 0, 0, 0}
} else {
dp[i] = []int{nums[i] + dp[i-1],
max(dp[i-1], dp[i-1]),
nums[i] + dp[i-1],
max(dp[i-1], dp[i-1])}
}

}
// don't choose the last item
v1 := max(dp[len(nums)-1], dp[len(nums)-1])
// choose the last item
v2 := dp[len(nums)-1]
return max(v1, v2)
}

func max(v1 int, v2 int) int {
if v1>v2 {
return v1
} else {
return v2
}
}
```

Share It, If You Like It.