image.png
    f(1)=nums[1]
    f(2)=max(nums[1],nums[2])
    如果要打劫第n家，就必然不能打劫第n-1家，所以打劫第n家得到的钱一共是第n家的钱加上前n-2家获得的最多的钱，即：f(n-2)+nums(n)，如果不打劫第n家，获得的最大收益就是f(n-1)，两者我们要去较大的那个，所以动态转移方程是：
    f(n)=max(nums[n]+f(n-2),f(n-1))

    1. package main
    3. import "fmt"
    5. func max(a,b int)int{
    6.     if a>b {
    7.         return a
    8.     }
    9.     return b
    10. }
    12. func rob(nums []int) int {
    13.     if len(nums)==0 {
    14.         return 0
    15.     }
    16.     if len(nums)==1 {
    17.         return nums[0]
    18.     }
    19.      dp := make([]int,len(nums))
    20.      dp[0] = nums[0]
    21.      dp[1] = max(nums[0],nums[1])
    22.      maxVal := dp[1]
    23.      for i:=2;i<len(nums);i++{
    24.          dp[i] = max(dp[i-1],dp[i-2]+nums[i])
    25.          maxVal = max(maxVal,dp[i])
    26.      }
    27.      return maxVal
    28. }
    30. func main() {
    31.     fmt.Println(rob([]int{1,2,3,1}))
    32.     fmt.Println(rob([]int{2,7,9,3,1}))
    33. }

    **