198.打家劫舍.md

198.打家劫舍

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2：

输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解法步骤

1. 确定dp数组（dp table）以及下标的含义
   1. dp[i]代表的是从第1号偷到当前第i号房间时，可以偷到的最大金额
2. 确定递推公式
   1. 偷到当前dp[i]也就是第i号房间时，有两种选择(状态)偷或者不偷 选择这两种获利最大的就是结果
      • 偷: 上家就不能偷，需要把偷到前面上上家dp[i-2]的金额和当前第i号房间算上，就是偷窃当前的总金额即dp[i] = dp[i-2]+nums[i]
      • 不偷: 偷到上家时最大金额也是偷到当前家的最大金额 即dp[i] = dp[i-1]
      • 当前房间最大获利dp[i] = 最大值(偷，不偷) = max(dp[i-2]+nums[i], dp[i-1])
3. dp数组如何初始化
   1. dp[0]只能选择偷 是最大的获利
   2. dp[1] 选择偷或者不偷
      • 偷： dp[1] = nums[1](前面dp[0]就不能算入了)
      • 不偷: dp[1] = nums[0]
      • 选取最大获利即是dp[1] max(nums[0], nums[1])
4. 确定遍历顺序
   1. 因为dp[0]、dp[1]即为第1、第2号房间初始化过了，那么循环从索引2开始即可
5. 举例推导dp数组
   1. 正常情况
   2. 特例, 如长度分别为0 1 2时验证结果

代码如下

func rob(nums []int) int {
    //特判
    if len(nums) == 0  {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }
    if len(nums) == 2 {
        return max(nums[0], nums[1])
    }


    //初始化dp数组
    dp := map[int]int{}
    dp[0], dp[1] = nums[0], max(nums[0], nums[1])
    for i:=2; i<len(nums); i++ {
        dp[i] = max(dp[i-2]+nums[i], dp[i-1])
    }

    return dp[len(nums)-1]
}

func max(p1, p2 int) int {
    if p1 > p2 {
        return p1
    }
    return p2
}