1、线性DP 213. 打家劫舍 II

//rob 0, not rob n-1 || not rob 0,not rob n-1 ==>rob(0,nums.length-2,nums)

//not rob 0,rob n-1 || not rob 0,not rob n-1;==>rob(1, nums.length-1, nums)

func rob(nums []int) int {

    n := len(nums)

    if n == 0{

        return 0

    }

    if n == 1{

        return nums[0]

    }

    return MAX(help(nums,0,n-1),help(nums,1,n))

}
//由题意抢了第一家则不能抢最后一家;抢了最后一家就不能抢第一家。

//抢了第一家的最大值就是在nums[:n-1)中抢的，抢了最后一家的最大值，就是在nums[1:]抢的

func help(nums []int,begin,end int) int{

    curMax,preMax := 0,0

    for i:=begin;i<end;i++{

        tmp := curMax

        curMax = MAX(curMax,preMax+nums[i])

        preMax =  tmp

    }

    return curMax

}
func MAX(i,j int) int{

    if i<j{

        return j

    }else{

        return i

    }

}