企业官网建设流程全解析

题目分析

LeetCode 198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，唯一的限制是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组 nums，计算在不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例：

• 输入：nums = [1,2,3,1]，输出：4（偷第 0 和第 2 间房，1 + 3 = 4）
• 输入：nums = [2,7,9,3,1]，输出：12（偷第 0、2、4 间房，2 + 9 + 1 = 12）

核心思路

这是一道经典的线性动态规划问题，属于"不能选相邻元素的最大化收益"模型。

对于每一间房屋，只有两种选择：

• 偷：当前收益 = 前前间房的最大收益 + 当前房屋金额
• 不偷：当前收益 = 前一间房的最大收益（继承之前的最优结果）

取两者中的较大值即可。

Java 实现

方法一：标准 DP 数组（O(n) 空间）

class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}

int n = nums.length; int[] dp = new int[n]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < n; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[n - 1]; }

}

状态定义： dp[i] 表示考虑前 i+1 间房屋（下标 0 到 i）时能偷到的最高金额。

状态转移方程： dp[i] = max(dp[i-1], dp[i-2] + nums[i])

• dp[i-1]：不偷第 i 间房，继承前一状态的最大值
• dp[i-2] + nums[i]：偷第 i 间房，则不能偷第 i-1 间，需加上第 i-2 间状态的最大值

方法二：空间优化（O(1) 空间，面试标准答案）

由于 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，可以用两个变量滚动更新，将空间复杂度降至 O(1)。

class Solution {
public int rob(int[] nums) {
int prev2 = 0; // 代表 dp[i-2]，即前前间房的最大收益
int prev1 = 0; // 代表 dp[i-1]，即前一间房的最大收益

for (int num : nums) { int cur = Math.max(prev1, prev2 + num); prev2 = prev1; prev1 = cur; } return prev1; }

}

执行过程（以 nums = [2,7,9,3,1] 为例）：
轮次 当前房屋金额 prev2 prev1 cur（当前最大收益）
初始 — 0 0 —
第1轮 2 0 0 max(0, 0+2) = 2
第2轮 7 0 2 max(2, 0+7) = 7
第3轮 9 2 7 max(7, 2+9) = 11
第4轮 3 7 11 max(11, 7+3) = 11
第5轮 1 11 11 max(11, 11+1) = 12

最终返回 prev1 = 12 ✅

方法三：记忆化搜索（自顶向下）

class Solution {
private int[] memo;

public int rob(int[] nums) { memo = new int[nums.length]; Arrays.fill(memo, -1); return dfs(0, nums); } private int dfs(int i, int[] nums) { if (i >= nums.length) { return 0; } if (memo[i] != -1) { return memo[i]; } // 偷当前房屋 vs 不偷当前房屋 memo[i] = Math.max(nums[i] + dfs(i + 2, nums), dfs(i + 1, nums)); return memo[i]; }

}

复杂度分析
维度 方法一：DP 数组 方法二：空间优化 方法三：记忆化搜索
时间复杂度 O(n) O(n) O(n)
空间复杂度 O(n) O(1) O(n) 递归栈 + memo 数组

面试延伸

如果面试官追问，可以补充说明：

• 为什么不能贪心（只偷金额最大的）？ 因为相邻限制导致局部最优不等于全局最优，比如 [2,1,1,2]，贪心选 2+2=4，但 DP 也能得到 4；但 [1,2,3,1] 贪心可能选错。
• 如果房屋围成一圈怎么办？ 这就是 LeetCode 213. 打家劫舍 II，拆成两种情况分别 DP：不偷第一间房 vs 不偷最后一间房，取较大值。
• 如果房屋是二叉树结构怎么办？ 这就是 LeetCode 337. 打家劫舍 III，用树形 DP，每个节点返回"偷"和"不偷"两种状态的最大收益。
• 这道题的 DP 模型还能用在哪些场景？ “不能选相邻元素的最大化收益"模型非常通用，比如"删除并获得点数”（LeetCode 740）、"栅栏涂色"等都属于同一类变形。

这道题是动态规划的入门必刷题，和"爬楼梯"、"斐波那契数列"属于同一类递推模型，需要我顺带把打家劫舍系列的另外两道变形题（环形房屋、二叉树房屋）的思路也整理一下吗？