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][0]: with nums[0] selected, include nums[i]
// dp[i][1]: with nums[0] selected, exclude nums[i]
// dp[i][2]: with nums[0] not selected, include nums[i]
// dp[i][3]: with nums[0] 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[0] }

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

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

func max(v1 int, v2 int) int {
    if v1>v2 {
        return v1
    } else {
        return v2
    }
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.