题目

leetcode213:打家劫舍

代码与解析

本文思路参考自carl代码随想录
本道题目是成了一道环，
leetcode:198没有环
成环的话主要是考虑三种情况

• 不考虑首尾
  
• 考虑首，不考虑尾
  
• 考虑尾不考虑首
  
  但是，实际上只需要考虑两种情况，第二种和第三种
  第一种情况被第二种第三种包括了，
  这道题要把每一种情况拆出来，每一种具体情况和leetcode:198没有环很相似

// 实际上nums数组可以值传递，不需要引用传递，虽然这样可以提高效率
func rob(nums []int) int {
    if len(nums)==1{
        return nums[0]
    }
    r1 := pack(0, len(nums)-2, &nums)
    r2 := pack(1,len(nums)-1,&nums)
    return max(r1, r2)
    // fmt.Println(dp)
    // return dp[len(nums)-1]
}
func pack(start, end int, nums *[]int)int{
    // fmt.Println("start:", start, "end:", end)
    if end==start{
        return (*nums)[end]
    }
    dp := make([]int, len(*nums))
    dp[start] = (*nums)[start]

    dp[start+1] = max((*nums)[start], (*nums)[start+1])
    // fmt.Println(dp)
    for i:=start+2;i<=end;i++{
        dp[i] = max(dp[i-2]+(*nums)[i],dp[i-1])
    }
    fmt.Println(dp)
    return dp[end]
}
func max(m,n int)int{
    if m>n{
        return m
    }
    return n
}