题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房屋内都藏有一定的现金，影响你偷窃的唯一制约因素就是：相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的整数数组 nums ，请你计算在不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
示例分析
示例 1
输入: nums = [1,2,3,1]
输出: 4
解释：
-
偷第 1 间房，可以拿到 1
-
偷第 3 间房，可以拿到 3
-
总金额为 4
不能连续偷第 2 间和第 3 间，因为它们是相邻的。
示例 2
输入: nums = [2,7,9,3,1]
输出: 12
解释：
-
偷第 1 间房，得到 2
-
偷第 3 间房，得到 9
-
偷第 5 间房，得到 1
总金额为 12。
解题思路
这道题是一道非常经典的动态规划题。
因为每一间房屋都只有两种选择：
-
偷这一间
-
不偷这一间
而一旦偷了当前房屋，就不能偷前一间；如果不偷当前房屋，那么前一间偷不偷都无所谓。
所以这道题的关键就是：走到当前位置时，最大收益是多少。
你给出的代码如下：
class Solution {
public int rob(int[] nums) {
int prev = 0;
int curr = 0;
for (int i : nums) {
int temp = Math.max(curr, prev + i);
prev = curr;
curr = temp;
}
return curr;
}
}
这份代码写得非常简洁，本质上就是把动态规划进行了空间优化。
状态定义
为了理解这份代码，我们先从最普通的动态规划思路开始。
设 dp[i] 表示：
偷到第
i间房屋时，能够获得的最大金额。
那么对于第 i 间房屋，有两种选择：
1. 不偷第 i 间
如果不偷当前房屋，那么最大收益就是前一间房屋时的最大收益：
dp[i - 1]
2. 偷第 i 间
如果偷当前房屋，那么前一间就不能偷，所以最大收益为：
dp[i - 2] + nums[i]
状态转移方程
所以可以得到状态转移公式：
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
这就是整道题最核心的地方。
意思非常简单：
-
要么不偷当前房屋，沿用前面的最优解
-
要么偷当前房屋，那么就只能接在前前间房屋的最优解后面
两种情况取最大值即可。
为什么可以用两个变量优化
观察状态转移方程：
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
可以发现，计算 dp[i] 时，其实只会用到：
-
dp[i - 1] -
dp[i - 2]
也就是说，我们没有必要真的开一个数组来保存所有状态，只需要两个变量就够了。
在你的代码中：
-
prev表示前前一间房屋的最大收益 -
curr表示前一间房屋的最大收益
然后用一个临时变量 temp 来表示当前房屋处理完之后的最大收益。
代码解析
1. 初始化
int prev = 0;
int curr = 0;
一开始还没有偷任何房子，所以最大收益都是 0。
这里可以理解为：
-
prev对应dp[i - 2] -
curr对应dp[i - 1]
2. 遍历每一间房屋
for (int i : nums) {
这里的 i 表示当前房屋中的金额。
3. 计算当前房屋的最优解
int temp = Math.max(curr, prev + i);
这里就是状态转移方程的压缩版：
当前最优解 = max(不偷当前房屋, 偷当前房屋)
= max(curr, prev + i)
-
curr：表示不偷当前房屋，直接沿用前面的最优解 -
prev + i：表示偷当前房屋，那么就只能加上前前一间房屋的最优解
4. 更新状态
prev = curr;
curr = temp;
状态向前推进一位：
-
原来的
curr变成下一轮的prev -
当前算出来的
temp变成下一轮的curr
5. 返回结果
return curr;
循环结束后，curr 就是最终答案。
示例推演
我们以数组：
nums = [2,7,9,3,1]
为例，来完整模拟一下。
初始状态：
prev = 0
curr = 0
遍历到 2
temp = max(0, 0 + 2) = 2
prev = 0
curr = 2
遍历到 7
temp = max(2, 0 + 7) = 7
prev = 2
curr = 7
遍历到 9
temp = max(7, 2 + 9) = 11
prev = 7
curr = 11
遍历到 3
temp = max(11, 7 + 3) = 11
prev = 11
curr = 11
遍历到 1
temp = max(11, 11 + 1) = 12
prev = 11
curr = 12
最终答案为：
12
为什么不能贪心
有些同学第一次做这题时，可能会想：
-
当前房屋金额大就偷
-
当前房屋金额小就不偷
这种贪心思路是不行的。
因为当前房屋是否值得偷，不仅取决于它本身的金额，还取决于它和前面房屋组合之后的总收益。
比如：
[2,1,1,2]
如果只看眼前，很容易做出错误选择。 正确答案是偷第 1 间和第 4 间，总金额为 4。
所以这题必须用动态规划，从整体最优的角度考虑。
复杂度分析
时间复杂度
O(n)
只遍历了一次数组。
空间复杂度
O(1)
没有使用额外的数组，只用了常数个变量。
和普通 DP 写法对比
普通 DP 写法
class Solution {
public int rob(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
}
这种写法更容易理解，但需要一个额外数组来存储状态。
空间优化写法
你给出的写法把 dp[i - 1] 和 dp[i - 2] 压缩成了两个变量：
class Solution {
public int rob(int[] nums) {
int prev = 0;
int curr = 0;
for (int i : nums) {
int temp = Math.max(curr, prev + i);
prev = curr;
curr = temp;
}
return curr;
}
}
这种写法更加简洁，也是面试中更推荐掌握的写法。
总结
这道题的核心就是这条状态转移方程：
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
理解这条式子之后，整道题就非常清楚了：
-
不偷当前房屋，就继承前一个状态
-
偷当前房屋，就加上前前一个状态
-
两者取最大值
-
由于只依赖前两个状态，所以可以用两个变量优化空间
这是一道非常经典的入门动态规划题，也是很多后续 DP 题的基础。 只要把这题吃透，后面很多“选或不选”的题目都会顺手很多。
