LC198. 打家劫舍

题目描述

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

题目解析

题目在说什么

想象你是一个小偷，面前有一排房子，每个房子里都有一些钱。但是这些房子装了警报系统：如果你连续偷两间相邻的房子，警报就会响，你就会被抓。所以你的目标是：在不触发警报（不偷相邻房子）的前提下，偷到最多的钱。

比如，房子里的钱是 [1, 2, 3, 1]。你可以偷第1间（1元）和第3间（3元），总共4元。如果你偷第2间（2元）和第4间（1元），总共3元，不如4元多。所以答案是4。

这个问题其实是一个经典的“动态规划”问题，但别被名字吓到，它本质上就是“做决策时，每一步都选最好的”。

---

思路是怎么来的

第一步：从最简单的情况开始想

• 如果只有一间房子，那没得选，只能偷它，金额就是这间房子的钱。
• 如果有两间房子，你不能同时偷两间（因为相邻），所以只能选钱多的那间偷。

第二步：扩展到三间房子

假设房子编号是1、2、3，金额分别是 a、b、c。现在你要决定偷不偷第3间房子。

• 如果你偷第3间，那么第2间就不能偷，你只能从第1间开始考虑。所以总金额 = 第3间的钱 + 前1间能偷到的最大金额。
• 如果你不偷第3间，那么你可以从第1、2间里选，但注意：不偷第3间不代表你一定能偷第2间，因为第2间可能和第1间冲突。实际上，不偷第3间时，你面临的情况就是“前两间房子能偷到的最大金额”。

所以，对于第3间房子，你的最优选择就是比较上面两种情况，取较大的那个。

第三步：推广到任意第 i 间房子

对于第 i 间房子，你的决策就是：

• 偷它：那么第 i-1 间就不能偷，所以总金额 = 第 i 间的钱 + 前 i-2 间能偷到的最大金额。
• 不偷它：那么总金额 = 前 i-1 间能偷到的最大金额。

你只需要每次选两者中较大的那个。这就是整个问题的核心思路。

生活化比喻：就像你吃自助餐，每道菜（房子）旁边都有一道“相邻菜”不能同时拿。你走到第 i 道菜前，要么拿它（放弃前一道），要么不拿它（保留前一道的选择）。每次你都要权衡哪个更划算。

---

代码逐步拆解

我们来看参考代码，一行一行解释。

int n = nums.length;

获取房子的总数。比如 [1,2,3,1] 有4间，n=4。

if(n == 0) return 0;

如果数组为空（没有房子），当然偷不到钱，直接返回0。

if(n == 1) return nums[0];

如果只有一间房子，直接偷它，返回它的金额。

int[] value = new int[n + 1];

创建一个数组 value，长度是 n+1。为什么多一个？因为我们要用 value[0] 表示“前0间房子”能偷的最大金额（即0），value[1] 表示“前1间房子”能偷的最大金额，以此类推，直到 value[n] 表示所有房子。

value[0] = 0;

前0间房子，没得偷，金额是0。

value[1] = nums[0];

前1间房子，就是第一间房子，金额就是 nums[0]（注意数组下标从0开始）。

for(int i = 2 ; i <= n ; i++){

从 i=2 开始，一直到 i=n，依次计算前 i 间房子的最优金额。

value[i] = Math.max(value[i - 1] , value[i - 2] + nums[i - 1]);

这是核心公式：

• value[i-1]：不偷第 i 间房子，那么前 i-1 间的最优结果就是 value[i-1]。
• value[i-2] + nums[i-1]：偷第 i 间房子，那么第 i-1 间就不能偷，所以前 i-2 间的最优结果加上第 i 间的钱（nums[i-1] 因为数组下标从0开始）。

取两者中较大的，就是前 i 间房子的最优结果。