Leetcode 198

Topic link

From this paragraph in the code below

    a0 := nums[0]
    a1 := nums[1]
    a2 := a0+nums[2]
Copy the code

From index 3, the maximum amount after stealing house I is obtained by adding “the maximum value of A0 and A1” and the amount in house I. Since A2 contains A0, and A0, A1 and A2 are updated iteratively, each house I only needs to consider A0 and A1. The following code is simplified from the basis of one-dimensional DP array. If it is not easy to understand, please write a realization based on one-dimensional DP array first.

func rob(nums []int) int {
    l := len(nums)
    if l == 0 {
        return 0
    }
    if l == 1 {
        return nums[0]}if l == 2 {
        return max(nums[0], nums[1])}// l > 2
    a0 := nums[0]
    a1 := nums[1]
    a2 := a0+nums[2]
    for i := 3; i < l; i++ {
        // Do not steal adjacent houses
        temp := nums[i] + max(a0,a1)
        a0 = a1
        a1 = a2
        a2 = temp
    }
    return max(a1,a2)
}

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