198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

  1. //本来就是一维，自顶向下，时空都是On
  2. func rob(nums []int) int {
  3.     if len(nums) == 0 {
  4.         return 0
  5.     }
  6.     if len(nums) == 1 {
  7.         return nums[0]
  8.     }
  10.     dp := make([]int, len(nums))
  11.     dp[0] = nums[0]
  12.     dp[1] = max(nums[0], nums[1])
  14.     for i := 2; i < len(nums); i++ {
  15.         dp[i] = max((dp[i-2] + nums[i]), dp[i-1])        //考虑本次打劫+权重，和上次是否打劫
  16.     }
  17.     return dp[len(nums) - 1]
  18. }
  20. func max(x, y int) int {
  21.     if x > y {
  22.         return x
  23.     }
  24.     return y
  25. }
//一维里，就不用降维了，直接滚动数组优化空间O1，记忆化
func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }

    first := nums[0]                    //==dp[i-2]
    second := max(nums[0], nums[1])     //==dp[i-1]
    temp := 0

    for i := 2; i < len(nums); i++ {    //dp[i] == dp[i-1],dp[i-2]
        temp = max(first + nums[i], second)
        first = second
        second = temp                    //first, second = second, max((first + nums[i]), second)
    }
    return second
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}