LeetCode: House Robber II

## https://code.dennyzhang.com/house-robber-ii
## Basic Ideas: dynamic programming
##
##  Rob house one by one, from left to right
##  For each house, we can choose rob it or not
##
##  What about the last house?
##    If we don't rob it, consider nums[...:n-1]
##    If we rob it, consider nums[1:n-2]
##
## Complexity: Time O(n), Space O(1)
class Solution:
    def rob(self, nums: List[int]) -> int:
        def myRob(nums):
            n = len(nums)
            prevMax, curMax = 0, 0
            for i in range(n):
                tmp = curMax
                # don't take vs take
                curMax = max(curMax, nums[i]+prevMax)
                prevMax = tmp
            return curMax
        n = len(nums)
        if n==0: return 0
        if n==1: return nums[0]
        # don't take last item vs take last item
        return max(myRob(nums[0:n-1]), myRob(nums[1:n-2])+nums[-1])

// 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
    }
}