[leetcode]198-打家劫舍

来源：力扣 （LeetCode）

链接：https://leetcode-cn.com/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 。

二、题解

假设当前是第 n 家房屋，已经偷到了 x 元。当前有两种选择：偷或者不偷。

1. 如果偷了，那么说明前面一家房屋是不能偷的，否则会报警。这个时候偷到的金额为 x[n - 2] + nums[n] 。
2. 如果不偷，说明前面一家房屋肯定是要偷的，不然少偷了一家。这个时候偷到的金额为 x[n - 1] 。

两种情况，如何选择？肯定是选择两者中金额更大的，那么就能得到状态转移方程为：

$$dp[i]=max(dp[i - 1], dp[i - 2] + nums[i])$$

因为当前状态只于前面两个状态有关，因此没必要分配 dp 数组，使用固定的变量来表示就行了 （和斐波那契数列一样） 。状态转移方程可修改为：

$$amount = max(prev, pprev + nums[n])$$

其中 prev 是上一个状态的最大值，pprev 是上上个状态的最大值，nums[n]是当前第 n 个房屋的金额。\(\)

三、代码