题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）

• 链接：https://leetcode.cn/problems/house-robber/
  

• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

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

示例 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 <= nums.length <= 100
  

• 0 <= nums[i] <= 400
  

思路

一眼动态规划，这道题最大的收获是远超官方题解数据，哈哈哈，撒花撒花~

• dp 数组含义：

• dp[i][0]、dp[i][1] 含义是不偷、偷第 i 家的最大收获

• 状态转移方程：

• dp[i][0] = max(dp[i][0], dp[i][1])
  

  dp[i][1] = max(dp[i][0] + nums[i], dp[i][1])
  

• 初始化：

• dp[0][0] = 0dp[0][1] = nums[0]
  

其实代码基本就出来了，但是这个虽然时间复杂度挺高，但是空间复杂度还是会很高的，所以来优化一下吧！

其实很容易发现，在状态转移方程里，偷不偷下一家的数据，只跟上一家的数据有关，那么这里就可以使用滚动数组的思路来优化空间了：

只定义一个两个位置的数组, dp[0]代表不偷当前家的最大值，dp[1]代表偷当前家的最大值

具体逻辑很类似，直接上代码，细节都在注释了

代码

func rob(nums []int) int {    // dp[0] 含义是不偷当前家的最大值    // dp[1] 含义是偷当前家的最大值    dp := make([]int, 2)    // 初始化数据，第一家偷的最大值，第一家不偷的值正好等于初始化值0    dp[1] = nums[0]    n := len(nums)    // 循环使用的辅助变量    temp0 := 0    for i := 1; i < n; i++ {        // 缓存上一家不偷的结果值        temp0 = dp[0]        // 滚动数组方式，节省空间复杂度        // 计算出这一家不偷、偷的结果值        dp[0] = max(dp[1], temp0)        dp[1] = max(dp[1], temp0+nums[i])    }    return max(dp[0], dp[1])}

欢迎关注公众号交流更多题目~