198. 打家劫舍

Go示例

func max(a, b int) int {
    if a > b {
        return a
    }
    return b 
}

func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    if len(nums) == 1 {
        return nums[0]
    }

    n := len(nums)
    dp := make([]int, n)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i:= 2; i < n; i++ {
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    }
    return dp[n - 1] 
}

拓展题目，213. 打家劫舍2，将房子连成环了，怎么去修改上面的代码？

思路是分成两个子串进行讨论

• 取第 0 个元素，那么最后一个元素不能取，子串的范围是 [0, n - 2]
• 取第 1 个元素，最后一个元素是可以取的，子串的范围是 [1, n - 1]

func max(a, b int) int {
    if a > b {
        return a
    }
    return b 
}

func subRob(nums []int, start, end int) int { // 打家劫舍
    n := len(nums)
    dp := make([]int, n)
    dp[start] = nums[start]
    dp[start + 1] = max(nums[start], nums[start + 1])
    for i := start + 2; i <= end; i++ {
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    }
    return dp[end]
}
func rob(nums []int) int { // 分情况讨论
    n := len(nums)
    if n == 1 { return nums[0]}
    if n == 2 { return max(nums[0], nums[1]) }
    return max(subRob(nums, 0, n - 2), subRob(nums, 1, n - 1))
}